Fibonacci / Binomial coefficient identity

Here’s an identity relating Fibonacci numbers and binomial coefficients.

F_{n+1} = {n \choose 0} + {n-1 \choose 1} + {n-2\choose 2} + \cdots

You can think of it as a finite sum or an infinite sum: binomial coefficients are zero when the numerator is an integer and the denominator is a larger integer. See the general definition of binomial coefficients.

Source: Sam E. Ganis. Notes on the Fibonacci Sequence. The American Mathematical Monthly, Vol. 66, No. 2 (Feb., 1959), pp. 129-130

More Fibonacci number posts:

One thought on “Fibonacci / Binomial coefficient identity

  1. I have seen this identity before, in the form of sums of diagonals taken from Pascal’s triangle. But I had only ever seen a (messy, algebraic) proof by induction. Looking at the equation just now, however, I realized there is a nice combinatorial proof. The Fibonacci number F_{n+1} counts the number of ways to tile a 1xn rectangle with a collection of 1×1 and 1×2 tiles. (The last tile can either be a 1×1, in which case there are F_n ways to tile the remaining n-1 tiles, or 1×2, in which case there are F_{n-1} ways to tile the remaining n-2; the sum of these gives F_{n+1}.) The right-hand side of the identity counts the same tilings, organized by how many 1×2 tiles there are: we could use n 1×1 tiles and pick 0 places to put 1×2 tiles; or we could have 1 1×2 tile and pick a spot to place it among the n-1 total tiles; or we could have 2 1×2 tiles and pick 2 spots for them among the n-2 tiles; and so on.

Leave a Reply

Your email address will not be published. Required fields are marked *