×

# 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, 10 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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, 10 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, 10 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, 10 months ago

You can use Binet's Formula to find the n-th Fibonacci number. It is easy to prove by induction.

- 4 years, 10 months ago

I know the formula for the nth Fibonacci number, I'm asking for the formula for the recurrence stated. (including Fibonacci Sequence)

- 4 years, 10 months ago