Combinatorial Identities
Most identities involving Fibonacci numbers can be proven using combinatorial arguments using the fact that Fn can be interpreted as the number of sequences of 1s and 2s that sum to n − 1. This can be taken as the definition of Fn, with the convention that F0 = 0, meaning no sum will add up to −1, and that F1 = 1, meaning the empty sum will "add up" to 0. Here the order of the summand matters. For example, 1 + 2 and 2 + 1 are considered two different sums.
For example, the recurrence relation
or in words, the nth Fibonacci number is the sum of the previous two Fibonacci numbers, may be shown by dividing the F(n) sums of 1s and 2s that add to n−1 into two non-overlapping groups. One group contains those sums whose first term is 1 and the other those sums whose first term is 2. In the first group the remaining terms add to n−2, so it has F(n−1) sums, and in the second group the remaining terms add to n−3, so there are F(n−2) sums. So there are a total of F(n−1)+F(n−2) sums altogether, showing this is equal to F(n).
Similarly, it may be shown that the sum of the first Fibonacci numbers up to the nth is equal to the n+2nd Fibonacci number minus 1. In symbols:
This is done by dividing the sums adding to n+1 in a different way, this time by the location of the first 2. Specifically, the first group consists of those sums that start with 2, the second group those that start 1+2, the third 1+1+2, and so on, until the last group which consists of the single sum where only 1's are used. The number of sums in the first group is F(n), F(n-1) in the second group, and so on, with 1 sum in the last group. So the total number of sums is F(n) + F(n − 1) + ... + F(1)+1 and therefore this quantity is equal to F(n + 2)
A similar argument, grouping the sums by the position of the first 1 rather than the first 2, gives two more identities:
and
In words, the sum of the first Fibonacci numbers with odd index up to F2n-1 is the (2n)th Fibonacci number, and the sum of the first Fibonacci numbers with even index up to F2n is the (2n+1)th Fibonacci number minus 1.
A different trick may be used to prove
or in words, the sum of the squares of the first Fibonacci numbers up to Fn is the product of the nth and (n + 1)th Fibonacci numbers. In this case note that Fibonacci rectangle of size Fn by F(n + 1) can be decomposed into squares of sizea Fn, Fn − 1, and so on to F1=1, from which the identity follows by comparing areas.
Read more about this topic: Fibonacci Number