Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$; I was stuck with this question for a while... Help me please!!! Thanks!!!
Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$
-
0I'm not sure why this is getting "voted to close" when it is the post that is _cited_ as duplicated _by_ this later post: http://math.stackexchange.com/questions/988450/inductive-proof-of-the-identity-binomn-0-f-0-binomn1-f-1-binomn2 – 2016-01-24
3 Answers
I accidentally stumbled across this old question while studying some facts about generating functions and could not resist posting this answer. Take an ordinary generating function of the LHS: $G(x)=\sum_{n\ge0}\sum_{0\le k\le n}\left(\begin{array}{c} n\\ k \end{array}\right)F_kx^n$ Change the order of summation to obtain
$G(x)=\sum_{k\ge0}\sum_{n\ge k}\left(\begin{array}{c} n\\ k \end{array}\right)F_kx^n=\sum_{k\ge0}F_k\sum_{n\ge0}\left(\begin{array}{c} n+k\\ k \end{array}\right)x^{n+k}\\=\sum_{k\ge0}F_kx^k\sum_{n\ge0}\left(\begin{array}{c} n+k\\ n \end{array}\right)x^n=\sum_{k\ge0}F_kx^k\frac{1}{\left(1-x\right)^{1+k}}\\=\frac{1}{1-x}\sum_{k\ge0}F_k\left(\frac{x}{1-x}\right)^k$ Now the expression under the sum is just the ordinary generating $F(z)$function for $F_n$ $F(z)=\frac{z}{1-z-z^2}$ where $z=\frac{x}{1-x}$. Substituting we obtain $G(x)=\frac{x}{1-3x-x^2}$ The last expression is the generating function for $F_{2n}$ as can be ascertained by calculating $\frac{1}{2}\left[F(x)+F(-x)\right]$
A counting argument:
The number of ways of climbing $n$ stairs, taking $1$ or $2$ steps at a time is $F_n$ (Try proving it).
Now suppose we had to climb $2n$ stairs. Note that we need to take at least $n$ moves.
We now consider the position after taking exactly $n$ moves. For each such position, we consider where we are and how many ways we can cover the rest.
This we do by considering the number of steps of $2$ we take.
If we take $k$ steps of $2$, then we take $n-k$ steps of $1$ for the first $n$ moves. We end up at step $n+k$, thus leaving $n-k$ steps to cover. These $n-k$ steps can be covered in $F_{n-k}$ ways and the number of ways of getting there is same as the number of ways of choosing $k$ moves of $2$ from $n$, which is $\binom{n}{k}$.
Thus as $k$ ranges from $0$ to $n$, we have that the number of ways of covering $2n$ stairs is
$F_{2n} = \sum_{k=0}^{n} \binom{n}{k} F_{n-k}$
Since $\binom{n}{k} = \binom{n}{n-k}$ we get
$ \binom{n}{0}F_0 + \binom{n}{1}F_1 + \dots + \binom{n}{n}F_n = F_{2n}$
A simple generalization of this argument gives us, for $2n \le m$
$ \binom{n}{0} F_{m-2n} + \binom{n}{1} F_{m-2n+1} + \dots + \binom{n}{n} F_{m-n} = F_m$
Hint: Binet's formula + Binomial formula. Also, $\varphi^2=\varphi+1$ and $\varphi^{-2}=2-\varphi$.
$\hskip 1.5in \displaystyle \sum_{\ell=0}^n \binom{n}{\ell}\frac{\varphi^\ell-(1-\varphi)^\ell}{\sqrt5}=\frac{(1+\varphi)^{\ell}-(2-\varphi)^\ell}{\sqrt5}=F_{2n} $