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?

When Pascal's triangle is made in non-lopsided fashion, each number is the sum of the numbers directly above-and-left and above-and-right.  In the lopsided manner presented, each number is the sum of the number directly above and the one above and to the left.

Each number that is directly above is part of the preceding diagonal line.  Each number that is above and to the left is part of the diagonal line before that.  So no number is added in that is not part of one of the two preceding diagonal lines

Also, every number on the diagonal before the current one has a number just below it and so is included in the current diagonal. Also every number in the diagonal before that has a number down and to the right of it and also is represented in the current diagonal.  So every number on one of the two preceding diagonals is included in the current line.

No number so included is included more than once.

Therefore the sum of the numbers on the current diagonal equals the sum of the numbers on the preceding diagonal plus the sum of the numbers on the diagonal before that.  This meets the definition of the Fibonacci sequence.

Posted by Charlie on 2004-03-15 14:11:08