Main Applications Identities History FAQ Algorithms

Proof of Pascal's Triangle to the Fibonacci numbers

  For this particular identity, it is easier to see if we draw the triangle so that the columns go straight up and down instead of on the diagonal.  We will use different colors (red, blue and green) to show the sums we want; the sums after the ...are the sums of  the color diagonal that begins with the first number in that row.


     
1  0  0  0  0  0 ...   1=1
1  1   0    0  0  0 ...   1+0=1
1  2  1  0  0    0 ...   1+1+0=2
1  3  3  1  0  0 ...   1+2+0+0=3
1  4  6  4  1  0 ...   1+3+1+0+0=5
1  5 10 10  5  1 ...   1+4+3+0+0+0=8
...

So the first few numbers in our list agree with the Fibonacci numbers, but can we be assured that the pattern will continue?  Now we use the additive identities of the Fibonaccis and Pascal's Triangle to show the pattern will work forever.

Take any two consecutive diagonal sums, say a red one and the green one to its right; in this form of Pascal's Triangle, when we add two consecutive numbers together on a row, it adds up to the number directly below the rightmost number; in this example, the number directly below any green number must be blue, which is the sum of red+green.  The only numbers in the matrix that might be missing from either the sum or the summands are zeros, so we get diagonal_n+diagonal_n+1 = diagonal_n+2 and we are done.