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

Fibonacci Numbers

F₁ = 1

Fun Facts about Fibonacci Numbers

F_m+n=F_m+1F_n+F_mF_n-1 

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

F_m+2 = F_m+1 + F_m = F_m+1F₂ + F_mF₁ 

F_m+3 = F_m+1 + F_m+2 = 2F_m+1 + F_m = F_m+1F₃ + F_mF₂ 

Now, for the induction step,

F_m+n = F_m+n-2 + F_m+n-1 
        = F_m+1F_n-2 + F_mF_n-3 + F_m+1F_n-1 + F_mF_n-2 
        = F_m+1(F_n-2+F_n-1) + F_m(F_n-3+F_n-2) 
        = F_m+1F_n + F_mF_n-1 

Fibonacci Sequence is infinite in both directions

By definition, F₀ = 0, F₁ = 1, and F_n = F_n-1 + F_n-2.  From this we see

F_n+1 = F_n + F_n-1,
F_n-1 = F_n+1 - F_n 

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)ⁿ F_n 

Proof by induction:

The base cases:
F₀ = -(-1)⁰ F₀ because F₀=0
F_-1 = -(-1)¹ F₁ because F_-1=F₁-F₀=1

Induction step for k=1,2,...:
F_-k = -(-1)^k F_k,
F_-k+1 = -(-1)^k-1 F_k-1.

Reformulating these, we have
-F_-k = (-1)^k F_k,
F_-k+1 = (-1)^k F_k-1 

Adding these, we have
F_-k+1-F_-k  = (-1)^k F_k F_k-1.

The left side is F_-k-1, and the right side is -(-1)^k+1 F_k+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,

F_m+n=F_m+1F_n+F_mF_n-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,

F_m+n+1=F_m+1F_n+1+F_mF_n 

F_m+n=F_m+1F_n+F_mF_n-1 

Subtracting the second from the first,

F_m+n-1=F_m+1F_n-1+F_mF_n-2 

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

Fooling around

F_m+n=F_m+1F_n+F_mF_n-1.

F_m+n=(F_m-1+F_m)(F_n-2+F_n-1)+(F_m-2+F_m-1)(F_n-3+F_n-2)

F_m+n=F_m-1F_n-2+F_mF_n-2+F_m-1F_n-1+F_mF_n-1+F_m-2F_n-3+F_m-1F_n-3+F_m-2F_n-2+F_m-1F_n-2 

F_m+n=+F_m-2F_n-3+F_m-2F_n-2+F_m-1F_n-3+2F_m-1F_n-2+F_m-1F_n-1+F_mF_n-2+F_mF_n-1 

 

d'Ocagne's identity: F_m F_n+1 - F_m+1 F_n = (-1)ⁿ F_m-n 

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

F_m-n=F_m+1F_-n+F_mF_-n-1 

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

F_m-n=-(-1)ⁿ F_m+1F_n+(-1)ⁿ F_mF_n+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 F₂:

	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 F_mF_n=F_pF_q 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 F_mF_n > F_pF_q.

Observation 3: In anti-diagonal x, which I define as the anti-diagonal that contains F_mF_n where m+n=x, the the largest Fibonacci Product is F_x-3F₃, and the smallest is F_x-2F₂.

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

F_x-2F₂ - F_x-4F₃ = F_x-5

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

F_x-2F₂, F_x-4F₄, F_x-6F₆, ..., F_x-5F₅, F_x-3F₃ 

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:

F_x-2F₂, F_x-4F₄, F_x-6F₆, ..., F_x/2F_x/2, F_x/2+1F_x/2-1, F_x/2+3F_x/2-3, ..., F_x-3F₃, and its successive differences are:
F_x-6, F_x-10, F_x-14, ..., F₂, 1, F₄, F₈, ..., F_x-8.

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

F_x-2F₂, F_x-4F₄, F_x-6F₆, ..., F_(x+1)/2F_(x-1)/2, F_(x+3)/2F_(x-3)/2, F_(x+7)/2F_(x-7)/2, ..., F_x-3F₃, and its successive differences are:
F_x-6, F_x-10, F_x-14, ..., F₃, 1, F₅, F₉, ..., F_x-8.

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

F_x-2F₂, F_x-4F₄, F_x-6F₆, ..., F_x/2+1F_x/2-1, F_x/2F_x/2, F_x/2+2F_x/2-2, ..., F_x-3F₃, and its successive differences are:
F_x-6, F_x-10, F_x-14, ..., F₄, 1, F₂, F₆, ..., F_x-8.

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

F_x-2F₂, F_x-4F₄, F_x-6F₆, ..., F_(x+3)/2F_(x-3)/2, F_(x+1)/2F_(x-1)/2, F_(x+5)/2F_(x-5)/2, ..., F_x-3F₃, and its successive differences are:
F_x-6, F_x-10, F_x-14, ..., F₅, 1, F₃, F₇, ..., F_x-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 m². 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 F_k = 0 and F_k+1 = 1 mod m, so in particular F_k is divisible by m.

GCD of two fibonacci numbers is a fibonacci number.

(proof? . . . . . .)

Sum of Fibonacci-related sequence 1/(F₁F₃) + 1/(F₂F₄) + 1/(F₃F₅) + ... = 1

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

Proof by induction that S_n = 1-1/(F_n+1F_n+2)

1/(F₁F₃) = 1/2 = 1-1/(F_n+1F_n+2)

S_n+1 = S_n + 1/(F_n+1F_n+3)
   = 1-1/(F_n+1F_n+2)+1/(F_n+1F_n+3)
   = 1-F_n+3/(F_n+1F_n+2F_n+3)+F_n+2/(F_n+1F_n+2F_n+3)
   = 1-(F_n+3-F_n+2)/(F_n+1F_n+2F_n+3)
   = 1-F_n+1/(F_n+1F_n+2F_n+3)
   = 1-1/(F_n+2F_n+3), proving the induction case

S_n = 1-1/(F_n+1F_n+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.