Fibonacci Numbers
   

   

 Math Help -> Basic Principles -> Recurrence Relations -> Fibonacci Numbers 

Fibonacci Numbers are a long studied sequence of numbers obeying a recurrence relation

Fibonacci Numbers

F0 = 0

F1 = 1

Fn = Fn-1 + Fn-2

Fun Facts about Fibonacci Numbers

Fm+n=Fm+1Fn+FmFn-1 

This can be proved by induction on n.  The two base cases are

Fm+2 = Fm+1 + Fm = Fm+1F2 + FmF1 

Fm+3 = Fm+1 + Fm+2 = 2Fm+1 + Fm = Fm+1F3 + FmF2 

Now, for the induction step,

Fm+n = Fm+n-2 + Fm+n-1 
        = Fm+1Fn-2 + FmFn-3 + Fm+1Fn-1 + FmFn-2 
        = Fm+1(Fn-2+Fn-1) + Fm(Fn-3+Fn-2) 
        = Fm+1Fn + FmFn-1 

Fibonacci Sequence is infinite in both directions

By definition, F0 = 0, F1 = 1, and Fn = Fn-1 + Fn-2.  From this we see

Fn+1 = Fn + Fn-1,
Fn-1 = Fn+1 - Fn 

So the familiar sequence, 0,1,1,2,3,5,8,13,21,... can be extended backwards, giving

...,-21,13,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,13,21,...

As you can see, the backwards extension of the Fibonacci numbers results in the same sequence, except with alternating signs.

F-n = -(-1)n Fn 

Proof by induction:

The base cases:
F0 = -(-1)0 F0 because F0=0
F-1 = -(-1)1 F1 because F-1=F1-F0=1

Induction step for k=1,2,...:
F-k = -(-1)k Fk,
F-k+1 = -(-1)k-1 Fk-1.

Reformulating these, we have
-F-k = (-1)k Fk,
F-k+1 = (-1)k Fk-1 

Adding these, we have
F-k+1-F-k  = (-1)k Fk Fk-1.

The left side is F-k-1, and the right side is -(-1)k+1 Fk+1, proving the induction case.

Most identities work for the extended Fibonacci numbers, but their induction proofs need "fixing" so they work backwards.  For example,

Fm+n=Fm+1Fn+FmFn-1 

has been proven by induction in the cases where m is any integer and n is a nonnegative integer.  What if n is negative?  For this, we need a new induction step, where we assume it's true for n and n+1, and we show it's true for n-1.  Starting from our earlier result in these two cases,

Fm+n+1=Fm+1Fn+1+FmFn 

Fm+n=Fm+1Fn+FmFn-1 

Subtracting the second from the first,

Fm+n-1=Fm+1Fn-1+FmFn-2 

So this identity is true for all integers m and n.

Fooling around

Fm+n=Fm+1Fn+FmFn-1.

Fm+n=(Fm-1+Fm)(Fn-2+Fn-1)+(Fm-2+Fm-1)(Fn-3+Fn-2)

Fm+n=Fm-1Fn-2+FmFn-2+Fm-1Fn-1+FmFn-1+Fm-2Fn-3+Fm-1Fn-3+Fm-2Fn-2+Fm-1Fn-2 

Fm+n=+Fm-2Fn-3+Fm-2Fn-2+Fm-1Fn-3+2Fm-1Fn-2+Fm-1Fn-1+FmFn-2+FmFn-1 

 

d'Ocagne's identity: Fm Fn+1 - Fm+1 Fn = (-1)n Fm-n 

Recall our earlier identity, Fm+n=Fm+1Fn+FmFn-1.  Now use -n in place of n, since the identity is valid for all integers:

Fm-n=Fm+1F-n+FmF-n-1 

Recall, also, that F-n = -(-1)n Fn, which means also that F-n-1 = (-1)n Fn+1.  Substituting these in the expression, above, gives us:

Fm-n=-(-1)n Fm+1Fn+(-1)n FmFn+1 

The result follows immediately.

If all the products of pairs Fibonacci numbers are listed in ascending sequence (A049997), then the differences between successive products (A049998) are all Fibonacci numbers.

Let's start by visualizing the Fibonacci Product Table, using a unique set of Fibonacci numbers beginning with F2:

 F2F3F4F5F6F7F8F9F10F11F12
F2123581321345589144
F32461016264268110178288
F436915243963102165267432
F551015254065105170275445720
F68162440641041682724407121152
F71326396510416927344271511571872
F8214263105168273441714115518693024
F934681021702724427141156187030264896
F105511016527544071511551870302548957920
F11891782674457121157186930264895792112816
F12144288432720115218723024489679201281620736

We will make some observations, and then prove them.

Observation 1: Fibonacci products are unique.  That is, if m>=n and p>=q and FmFn=FpFq then m=p and n=q.

Observation 2: Anti-diagonals are contiguous in the ascending sequence of Fibonacci Products.  That is, if m+n > p+q then FmFn > FpFq.

Observation 3: In anti-diagonal x, which I define as the anti-diagonal that contains FmFn where m+n=x, the the largest Fibonacci Product is Fx-3F3, and the smallest is Fx-2F2.

Observation 2+3: For any x, Fx-2F2 (the smallest element of anti-diagonal x) is larger than Fx-4F3 (the largest element of anti-diagonal x-1).  In fact, I can tell you exactly how much larger it is:

Fx-2F2 - Fx-4F3 = Fx-5

Observation 2, extended: The Fibonacci Products FmFn in anti-diagonal x, where m>=n and m+n=x, arranged in ascending sequence, are:

Fx-2F2, Fx-4F4, Fx-6F6, ..., Fx-5F5, Fx-3F3 

Observation 2, further extended for anti-diagonals, x, equivalent to 0, 1, 2, and 3 (mod 4):

If x is equivalent to 0 (mod 4), then the Fibonacci Products in that anti-diagonal, x, in sequence, are:

Fx-2F2, Fx-4F4, Fx-6F6, ..., Fx/2Fx/2, Fx/2+1Fx/2-1, Fx/2+3Fx/2-3, ..., Fx-3F3, and its successive differences are:
Fx-6, Fx-10, Fx-14, ..., F2, 1, F4, F8, ..., Fx-8.

If x is equivalent to 1 (mod 4), then the Fibonacci Products in that anti-diagonal, x, in sequence, are:

Fx-2F2, Fx-4F4, Fx-6F6, ..., F(x+1)/2F(x-1)/2, F(x+3)/2F(x-3)/2, F(x+7)/2F(x-7)/2, ..., Fx-3F3, and its successive differences are:
Fx-6, Fx-10, Fx-14, ..., F3, 1, F5, F9, ..., Fx-8.

If x is equivalent to 2 (mod 4), then the Fibonacci Products in that anti-diagonal, x, in sequence, are:

Fx-2F2, Fx-4F4, Fx-6F6, ..., Fx/2+1Fx/2-1, Fx/2Fx/2, Fx/2+2Fx/2-2, ..., Fx-3F3, and its successive differences are:
Fx-6, Fx-10, Fx-14, ..., F4, 1, F2, F6, ..., Fx-8.

If x is equivalent to 3 (mod 4), then the Fibonacci Products in that anti-diagonal, x, in sequence, are:

Fx-2F2, Fx-4F4, Fx-6F6, ..., F(x+3)/2F(x-3)/2, F(x+1)/2F(x-1)/2, F(x+5)/2F(x-5)/2, ..., Fx-3F3, and its successive differences are:
Fx-6, Fx-10, Fx-14, ..., F5, 1, F3, F7, ..., Fx-8.

Claim: By proving Observation 2, as further extended, immediately above, we will show that within any anti-diagonal, successive products are listed in sequence and differ by a Fibonacci number.  And by proving Observation 2+3, we will show that from one anti-diagonal to the next, successive products also differ by a Fibonacci number.  Together, these claims amount to a proof that all successive Fibonacci Products differ by a Fibonacci number.

. . . . . . .

For any natural number m, (m greater than 1) there exists a Fibonacci number which is divisible by m.

Let m be any natural number greater than 1.

Consider the sequence F(mod m), which is the sequence of least nonnegative residues of the terms of the Fibonacci sequence taken modulo m.

This sequence is infinite in both directions, because given any two consecutive terms, one can determine the preceding term and the following term.

Since the terms of F(mod m) range from 0 to m-1, the number of possible pairs of terms in the sequence is no larger than m2. And the entire sequence is determined by any pair of consecutive terms. So F(mod m) must be periodic.

If k is the period of F(mod m) then Fk = 0 and Fk+1 = 1 mod m, so in particular Fk is divisible by m.

GCD of two fibonacci numbers is a fibonacci number.

(proof? . . . . . .)

Sum of Fibonacci-related sequence 1/(F1F3) + 1/(F2F4) + 1/(F3F5) + ... = 1

Let Sn be defined as the partial sum of n terms.

Proof by induction that Sn = 1-1/(Fn+1Fn+2)

1/(F1F3) = 1/2 = 1-1/(Fn+1Fn+2)

Sn+1 = Sn + 1/(Fn+1Fn+3)
   = 1-1/(Fn+1Fn+2)+1/(Fn+1Fn+3)
   = 1-Fn+3/(Fn+1Fn+2Fn+3)+Fn+2/(Fn+1Fn+2Fn+3)
   = 1-(Fn+3-Fn+2)/(Fn+1Fn+2Fn+3)
   = 1-Fn+1/(Fn+1Fn+2Fn+3)
   = 1-1/(Fn+2Fn+3), proving the induction case

Sn = 1-1/(Fn+1Fn+2), which approaches 1 as n approaches infinity.

Internet References

Mathworld -- Fibonacci -- dozens and dozens of amazing facts about Fibonacci Numbers!

Mathworld -- Golden Ratio

The Fibonacci Sequence Module M -- including a proof that given any integer m, infinitely many Fibonacci numbers are divisible by m.

Related pages in this website

Linear Recurrence Relation -- a closed form solution

Fibonacci Numbers -- whose successive ratios approach the Golden Ratio

Recurrence Relation of Successive Powers of Polynomial Root -- what a mouthful!  The gist of this topic is that the successive powers of a root of a polynomial form a sequence that has an simple recurrence relation.

Unsolved Questions, including one asking whether there are an infinite number of prime Fibonacci Numbers

Recurrence Relation Puzzle 1, having to do with Fibonacci Numbers

Increasing Function Puzzle 1 -- Find the closed form of this function defined as a recurrence relation

Trig functions of Special Angles -- The golden ratio pops up here, too.

 

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]