 Application Center - Maplesoft

# Pascal's triangle and its relationship to the Fibonacci sequence

You can switch back to the summary page by clicking here.

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