Fibonacci Number - Combinatorial Identities

Combinatorial Identities

Most identities involving Fibonacci numbers can be proven using combinatorial arguments using the fact that F_n 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 F_n, with the convention that F₀ = 0, meaning no sum will add up to −1, and that F₁ = 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 F_2n-1 is the (2n)th Fibonacci number, and the sum of the first Fibonacci numbers with even index up to F_2n 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 F_n is the product of the nth and (n + 1)th Fibonacci numbers. In this case note that Fibonacci rectangle of size F_n by F(n + 1) can be decomposed into squares of sizea F_n, F_{n − 1}, and so on to F₁=1, from which the identity follows by comparing areas.