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