Consider the famous Pascal triangle, purposefully drawn in a somewhat lopsided way:

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
......................

Start at any number, and draw a line at 45 degrees, from bottom left to top right. (For example, if you chose the first "4" of the fifth row, the diagonal would also include a "1" and a "3")

How much do the numbers in such a line sum? Why? Can you prove it?

Pascal's triangle may be written down in terms of the binomial coefficients (n,m) as

(0,0)
(1,0) (1,1)
(2,0) (2,1) (2,2)
(3,0) (3,1) (3,2) (3,3)
(4,0) (4,1) (4,2) (4,3) (4,4)
(5,0) (5,1) (5,2),(5,3) (5,4) (5,5)
...
(n,0) (n,1) (n,2) (n,3) (n,4) (n,5) ... (n,n)
...

For m < 0 and m > n, (n,m) = 0.

Now

    (n,0) + (n-1,1) + (n-2,2) + ... =

 (n-1,0) + (n-2,1) + (n-3,2) + ... +

(n-1,-1) + (n-2,0) + (n-3,1) + ...

because each term of the top line of this formula is the sum of the two terms that lie below it in the next two lines, according to the usual formula (n,m) = (n-1,m) + (n-1,m-1) used to form Pascal's triangle. For n=0 and 1, the totals are each 1. Hence the result is the Fibonacci numbers because the lines of the formula are three consecutive diagonal sums of the type being treated in this problem, related by the Fibonacci recurrence relation F(n) = F(n-1) + F(n-2).

Edited on March 15, 2004, 7:23 pm

Posted by Richard on 2004-03-15 19:16:27