2000 Waterloo Maple Inc.

> restart:

An interesting property of Pascal's Triangle is that its diagonals sum to the Fibonacci sequence, as shown in the picture below:

It will be shown that the sum of the entries in the n -th diagonal of Pascal's triangle is equal to the n -th Fibonacci number for all positive integers n . Suppose = sum of the n -th diagonal and is the n- th Fibonacci number, for n >= 0. This property will be proven using the Principle of Mathematical Induction.

Base Case:

For n = 0, = binomial(0,0) = 1, and 1 is the zeroth Fibonacci number, . Therefore, the result is true for n = 0.

Inductive Hypothesis:

Assume that that = , for n = 0, ..., k .

Inductive Conclusion:

It must be shown that = , for all k > 0.

By the property of the Fibonacci sequence, , for all k > 1.

Furthermore, by the inductive hypothesis, = and = .

Therefore, = + .

Observe the following:

= binomial(0,0) = 1 =
= binomial(1,1) = 1 =
= binomial(2,2) + binomial(1,0) = 2 =
= binomial(3,3) + binomial(2,1) = 3 =
= binomial(4,4) + binomial(3,2) + binomial(2,0) = 5 =
= binomial(5,5) + binomial(4,3) + binomial(3,1) = 8 =
= binomial(6,6) + binomial(5,4) + binomial(4,2) + binomial(3,0) = 13 =
= binomial(7,7) + binomial(6,5) + binomial(5,3) + binomial(4,1) = 21 =

Therefore it is easy to see that,
= binomial( n , n ) + binomial( n -1, n -2) + binomial( n -2, n -4) + ... =

Thus, it must be shown that,
=
+ , for all k > 0.

Without loss of generality, assume k is odd. Thus, the above equation simplifies to the following:
=
+ .

Maple can be now be used to help simplify the summations in the above equation to show the left-hand side is equal to the right-hand side:

> assume(k,odd): interface(showassumed=0):

> lhSide:=Sum(binomial(k-j+1,k-2*j+1),j=0..1+(k-1)/2);

> value(%);

> simplify(expand(%));

> lhSide_final := %:

> rhSide:=Sum(binomial(k-j,k-2*j),j=0..1+(k-3)/2)+Sum(binomial(k-j-1,k-2*j-1),j=0..1+(k-3)/2);

> value(%);

> simplify(expand(%));

> rhSide_final := %:

> is(lhSide_final=rhSide_final);

Thus = , for all odd k > 0. In a similar fashion, this result can be proven for even values of k . Therefore, by the Principle of Mathematical Induction, the sum of the entries in the n -th diagonal of Pascal's triangle is equal to the n -th Fibonacci number for all positive integers n . QED