July 24, 2011

fibonacci numbers in pascal's triangle

Fibonacci numbers in pascal's triangle?

The Proof follows from the following identity:
Let F(r) be the r-Th Fibonacci number, C(n,r) be the number of combination of n things taken are at a time and [x] be the greatest integer function then
Summation C(n-k, k) = F(n+1)
where k goes form k=0 to k = [n/2]
Now use induction on the variable n.