
Fibonacci Numbers are a long studied sequence of numbers obeying a recurrence relation
F_{1} = 1
F_{n} = F_{n1} + F_{n2}F_{m+n}=F_{m+1}F_{n}+F_{m}F_{n1}
This can be proved by induction on n. The two base cases are
F_{m+2} = F_{m+1} + F_{m} = F_{m+1}F_{2} + F_{m}F_{1}
F_{m+3} = F_{m+1} + F_{m+2} = 2F_{m+1} + F_{m} = F_{m+1}F_{3} + F_{m}F_{2}
Now, for the induction step,
F_{m+n} = F_{m+n2} + F_{m+n1}
= F_{m+1}F_{n2} + F_{m}F_{n3} + F_{m+1}F_{n1} + F_{m}F_{n2}
= F_{m+1}(F_{n2}+F_{n1}) + F_{m}(F_{n3}+F_{n2})
= F_{m+1}F_{n} + F_{m}F_{n1}
Fibonacci Sequence is infinite in both directions
By definition, F_{0} = 0, F_{1} = 1, and F_{n} = F_{n1} + F_{n2}. From this we see
F_{n+1} = F_{n} + F_{n1},
F_{n1} = 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)^{n} F_{n}
Proof by induction:
The base cases:
F_{0} = (1)^{0} F_{0} because F_{0}=0
F_{1} = (1)^{1} F_{1} because F_{1}=F_{1}F_{0}=1Induction step for k=1,2,...:
F_{k} = (1)^{k} F_{k},
F_{k+1} = (1)^{k1} F_{k1}.Reformulating these, we have
F_{k} = (1)^{k} F_{k},
F_{k+1} = (1)^{k} F_{k1}Adding these, we have
F_{k+1}F_{k} = (1)^{k} F_{k} F_{k1}.The left side is F_{k1}, 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+1}F_{n}+F_{m}F_{n1}
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 n1. Starting from our earlier result in these two cases,
F_{m+n+1}=F_{m+1}F_{n+1}+F_{m}F_{n}
F_{m+n}=F_{m+1}F_{n}+F_{m}F_{n1}
Subtracting the second from the first,
F_{m+n1}=F_{m+1}F_{n1}+F_{m}F_{n2}
So this identity is true for all integers m and n.
Fooling around
F_{m+n}=F_{m+1}F_{n}+F_{m}F_{n1}.
F_{m+n}=(F_{m1}+F_{m})(F_{n2}+F_{n1})+(F_{m2}+F_{m1})(F_{n3}+F_{n2})
F_{m+n}=F_{m1}F_{n2}+F_{m}F_{n2}+F_{m1}F_{n1}+F_{m}F_{n1}+F_{m2}F_{n3}+F_{m1}F_{n3}+F_{m2}F_{n2}+F_{m1}F_{n2}
F_{m+n}=+F_{m2}F_{n3}+F_{m2}F_{n2}+F_{m1}F_{n3}+2F_{m1}F_{n2}+F_{m1}F_{n1}+F_{m}F_{n2}+F_{m}F_{n1}
d'Ocagne's identity: F_{m} F_{n+1}  F_{m+1} F_{n} = (1)^{n} F_{mn}
Recall our earlier identity, F_{m+n}=F_{m+1}F_{n}+F_{m}F_{n1}. Now use n in place of n, since the identity is valid for all integers:
F_{mn}=F_{m+1}F_{n}+F_{m}F_{n1}
Recall, also, that F_{n} = (1)^{n} F_{n}, which means also that F_{n1} = (1)^{n} F_{n+1}. Substituting these in the expression, above, gives us:
F_{mn}=(1)^{n} F_{m+1}F_{n}+(1)^{n} F_{m}F_{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_{2}:
F_{2} F_{3} F_{4} F_{5} F_{6} F_{7} F_{8} F_{9} F_{10} F_{11} F_{12} F_{2} 1 2 3 5 8 13 21 34 55 89 144 F_{3} 2 4 6 10 16 26 42 68 110 178 288 F_{4} 3 6 9 15 24 39 63 102 165 267 432 F_{5} 5 10 15 25 40 65 105 170 275 445 720 F_{6} 8 16 24 40 64 104 168 272 440 712 1152 F_{7} 13 26 39 65 104 169 273 442 715 1157 1872 F_{8} 21 42 63 105 168 273 441 714 1155 1869 3024 F_{9} 34 68 102 170 272 442 714 1156 1870 3026 4896 F_{10} 55 110 165 275 440 715 1155 1870 3025 4895 7920 F_{11} 89 178 267 445 712 1157 1869 3026 4895 7921 12816 F_{12} 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_{m}F_{n}=F_{p}F_{q} then m=p and n=q.
Observation 2: Antidiagonals are contiguous in the ascending sequence of Fibonacci Products. That is, if m+n > p+q then F_{m}F_{n} > F_{p}F_{q}.
Observation 3: In antidiagonal x, which I define as the antidiagonal that contains F_{m}F_{n} where m+n=x, the the largest Fibonacci Product is F_{x3}F_{3}, and the smallest is F_{x2}F_{2}.
Observation 2+3: For any x, F_{x2}F_{2} (the smallest element of antidiagonal x) is larger than F_{x4}F_{3} (the largest element of antidiagonal x1). In fact, I can tell you exactly how much larger it is:
F_{x2}F_{2}  F_{x4}F_{3} = F_{x5}
Observation 2, extended: The Fibonacci Products F_{m}F_{n} in antidiagonal x, where m>=n and m+n=x, arranged in ascending sequence, are:
F_{x2}F_{2}, F_{x4}F_{4}, F_{x6}F_{6}, ..., F_{x5}F_{5}, F_{x3}F_{3}
Observation 2, further extended for antidiagonals, x, equivalent to 0, 1, 2, and 3 (mod 4):
If x is equivalent to 0 (mod 4), then the Fibonacci Products in that antidiagonal, x, in sequence, are:
F_{x2}F_{2}, F_{x4}F_{4}, F_{x6}F_{6}, ..., F_{x/2}F_{x/2}, F_{x/2+1}F_{x/21}, F_{x/2+3}F_{x/23}, ..., F_{x3}F_{3}, and its successive differences are:
F_{x6}, F_{x10}, F_{x14}, ..., F_{2}, 1, F_{4}, F_{8}, ..., F_{x8}.If x is equivalent to 1 (mod 4), then the Fibonacci Products in that antidiagonal, x, in sequence, are:
F_{x2}F_{2}, F_{x4}F_{4}, F_{x6}F_{6}, ..., F_{(x+1)/2}F_{(x1)/2}, F_{(x+3)/2}F_{(x3)/2}, F_{(x+7)/2}F_{(x7)/2}, ..., F_{x3}F_{3}, and its successive differences are:
F_{x6}, F_{x10}, F_{x14}, ..., F_{3}, 1, F_{5}, F_{9}, ..., F_{x8}.If x is equivalent to 2 (mod 4), then the Fibonacci Products in that antidiagonal, x, in sequence, are:
F_{x2}F_{2}, F_{x4}F_{4}, F_{x6}F_{6}, ..., F_{x/2+1}F_{x/21}, F_{x/2}F_{x/2}, F_{x/2+2}F_{x/22}, ..., F_{x3}F_{3}, and its successive differences are:
F_{x6}, F_{x10}, F_{x14}, ..., F_{4}, 1, F_{2}, F_{6}, ..., F_{x8}.If x is equivalent to 3 (mod 4), then the Fibonacci Products in that antidiagonal, x, in sequence, are:
F_{x2}F_{2}, F_{x4}F_{4}, F_{x6}F_{6}, ..., F_{(x+3)/2}F_{(x3)/2}, F_{(x+1)/2}F_{(x1)/2}, F_{(x+5)/2}F_{(x5)/2}, ..., F_{x3}F_{3}, and its successive differences are:
F_{x6}, F_{x10}, F_{x14}, ..., F_{5}, 1, F_{3}, F_{7}, ..., F_{x8}.Claim: By proving Observation 2, as further extended, immediately above, we will show that within any antidiagonal, successive products are listed in sequence and differ by a Fibonacci number. And by proving Observation 2+3, we will show that from one antidiagonal 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 m1, the number of possible pairs of terms in the sequence is no larger than m^{2}. 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 Fibonaccirelated sequence 1/(F_{1}F_{3}) + 1/(F_{2}F_{4}) + 1/(F_{3}F_{5}) + ... = 1
Let S_{n} be defined as the partial sum of n terms.
Proof by induction that S_{n} = 11/(F_{n+1}F_{n+2})
1/(F_{1}F_{3}) = 1/2 = 11/(F_{n+1}F_{n+2})
S_{n+1} = S_{n} + 1/(F_{n+1}F_{n+3})
= 11/(F_{n+1}F_{n+2})+1/(F_{n+1}F_{n+3})
= 1F_{n+3}/(F_{n+1}F_{n+2}F_{n+3})+F_{n+2}/(F_{n+1}F_{n+2}F_{n+3})
= 1(F_{n+3}F_{n+2})/(F_{n+1}F_{n+2}F_{n+3})
= 1F_{n+1}/(F_{n+1}F_{n+2}F_{n+3})
= 11/(F_{n+2}F_{n+3}), proving the induction caseS_{n} = 11/(F_{n+1}F_{n+2}), which approaches 1 as n approaches infinity.
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.
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.