# document.write (document.title)

 Math Help > Sequences and Series > 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

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:

 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F2 1 2 3 5 8 13 21 34 55 89 144 F3 2 4 6 10 16 26 42 68 110 178 288 F4 3 6 9 15 24 39 63 102 165 267 432 F5 5 10 15 25 40 65 105 170 275 445 720 F6 8 16 24 40 64 104 168 272 440 712 1152 F7 13 26 39 65 104 169 273 442 715 1157 1872 F8 21 42 63 105 168 273 441 714 1155 1869 3024 F9 34 68 102 170 272 442 714 1156 1870 3026 4896 F10 55 110 165 275 440 715 1155 1870 3025 4895 7920 F11 89 178 267 445 712 1157 1869 3026 4895 7921 12816 F12 144 288 432 720 1152 1872 3024 4896 7920 12816 20736

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 this Math Help site is Graeme McRae.