Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can someone explain how to prove the following identity involving Fibonacci sequence $F_n$

$F_{2n} = {n \choose 0} F_0 + {n\choose 1} F_1 + ... {n\choose n} F_n$ ?

share|improve this question
1  
Symbolically, this is similar to $${2n\choose n}={n\choose 0}\cdot{n\choose 0}+{n\choose 1}\cdot{n\choose 1}+\ldots+{n\choose n}\cdot{n\choose n}$$ –  Lucian Nov 17 '13 at 9:40
add comment

1 Answer

up vote 2 down vote accepted

Let $\alpha:=\displaystyle\frac{1+\sqrt5}2$ and $\beta:=\displaystyle\frac{1-\sqrt5}2$, then we have $$F_n=\frac{\alpha^n-\beta^n}{\sqrt5}\,.$$ Using this, $$\sum_{k\le n}\binom nk F_k=\frac1{\sqrt5}\left((1+\alpha)^n -(1+\beta)^n\right)\,.$$ Now $1+\alpha=\displaystyle\frac{3+\sqrt5}2=\alpha^2$ and similarly, $1+\beta=\beta^2$. (These were just the solutions of $x^2=x+1$.)

share|improve this answer
    
Can anyone think of a way of relating this identity to the staircase problem? The staircase problem is the number of ways of climbing an n-step staircase taking either 1 or 2 steps at a time. It is known that the number of ways is given by the Fibonacci numbers. –  ast Dec 16 '13 at 18:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.