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
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

2 Answers 2

up vote 3 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

Recall that $F_{2n+1}$ is the number of ways to tile a $1\times2n$-rectangle with squares and dominoes.

Let's focus on first $n$ tiles. We can choose which of them are squares in $\binom ni$ ways and the rest $(2n+1)-i-2(n-i)=i+1$ cells can be tiled in $F_i$ ways.

share|improve this answer

Your Answer


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.