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.

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

share|improve this question
    
Induction is sufficient. –  mez Feb 10 '13 at 13:41

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.