×

# Generalized Fibonacci Sequence

What is the formula for the generalized Fibonnaci sequence,

$$F_{n + k} = F_{n + k - 1} + F_{n + k - 2} + ... + F_{n}$$, where $$k \in \mathbb{N}$$

Note by Zi Song Yeoh
4 years, 4 months ago

Sort by:

You can solve using the characteristic equation (just wiki recurrence relations). Note that the sequence's general formula is dependent on what you choose for F1, F2 ... Fk - based on what the Fi are. · 4 years, 4 months ago

Indeed. Learn how to solve Linear Recurrence Relations using the characteristic equations.

The characteristic equation is $$x^k = x^{k-1} + x^{k-2} + \ldots + x^0$$, which has $$k$$ roots of the form $$\{ \alpha_i\}_{i=1}^k$$. Then, your sequence will have the value $$F_n = \sum A_i (\alpha_i)^n$$, where $$A_i$$ depends on the starting values that you chose. [Note: I glossed over the case of repeated roots, which have to be treated differently].

For example, when $$k = 2$$, then the equation is $$x^2 = x + 1$$ or equivalently $$x^2 - x - 1=0$$. This has roots $$\frac {1 \pm \sqrt{5} } {2}$$, and appear as the powers in Binet's formula. Staff · 4 years, 4 months ago

The formula involves the square root of 5, which I write as sqrt[5]. The nth Fibonacci is:

a*x^n + (1-a)*y^n

where a = (3+sqrt[5])/(5+sqrt[5]) x = (1+ sqrt[5])/2 y = (1- sqrt[5])/2

So my challenges to you are: first, to prove that the formula works, and second, to derive the equation you want for the sum of the first n terms, using the formula for the sum of a geometric series. · 4 years, 4 months ago

You can use Binet's Formula to find the n-th Fibonacci number. It is easy to prove by induction. · 4 years, 4 months ago