**Pascal's Triangle and it's Relationship
to the Fibonacci Sequence**
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