Some Proofs About Fibonacci Numbers: Relation 3

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up] [Next]

Relation 3

Below we will start with the recurrence deﬁnition (1) of F_n and repeatedly expand the higher index ﬁbonacci number present. Assume n to be large enough to allow some iterations.

Fn = Fn −2 + Fn −1 {expanding Fn −1} = Fn −2 + (Fn− 3 + Fn− 2) = F + (2)F n−3 n−2 {expanding Fn −2} = Fn −3 + (2)(Fn−4 + Fn−3) = (2)Fn−4 + (3)Fn−3 {repeatedly expanding as above} = (3)Fn−5 + (5)Fn−4 = (5)Fn−6 + (8)Fn−5

At each step, from aF_x + bF_x+1, we get:

aFx + b(Fx−1 + Fx) = bFx−1 + (a + b)Fx

Interestingly, the multipliers of the ﬁbonacci numbers are forming below sequence from one step to the next:

(1,1),(1,2),(2,3),(3,5),(5,8),...,(a,b),(b,a+ b),(a+ b,a + 2b)

where both terms in the pairs are forming a part of the ﬁbonacci sequence. So, we can write:

Fn = (1)Fn− 2 + (1)Fn−1 = (F )F + (F )F 1 n−2 2 n−1 = (F2 )Fn −3 + (F3)Fn −2 = (F3 )Fn −4 + (F4)Fn −3 = (F4 )Fn −5 + (F5)Fn −4 = ... = (F )F + (F )F 1 ≤ k ≤ (n − 2) k n−k−1 k+1 n−k

So, we can write below relation for all n > 2:

Fn = (F )F + (F )F 1 ≤ k ≤ (n − 2) k n−k−1 k+1 n−k

(4)

Note that for k = n − 2, we are back to the original recurrence deﬁnition of F_n:

Fn = (Fn− 2)F1 + (Fn− 1)F2 = Fn −2 + Fn −1

While the recurrence deﬁnition of F_n in (1) relates it only to the two preceding ﬁbonacci numbers (F_n−2,F_n−1), the equation (4) relates it to other lower indices ﬁbonacci numbers and will be very useful in ﬁnding other relations about ﬁbonacci numbers.

Example: for n = 10 and k = 6, F₁₀ = 55 = F₆F₃ + F₇F₄ = 8 ⋅ 2 + 13 ⋅ 3

[Prev] [Up] [Next]