1. ## Fibonacci Proof II

(n choose 0)*F(0) + (n choose 1)*F(1) + ... + (n choose n)*F(n)=F(2n)
I'm beginning to think induction is a bad approach...

2. Originally Posted by veronicak5678
(n choose 0)*F(0) + (n choose 1)*F(1) + ... + (n choose n)*F(n)=F(2n)
I'm beginning to think induction is a bad approach...
Let $\displaystyle \displaystyle \varphi=\frac{1+\sqrt{5}}{2}$, then a common fact (Binet's formula) says that $\displaystyle \displaystyle F_n=\frac{\varphi^n-\left(1-\varphi\right)^n}{\sqrt{5}}$. Thus,

\displaystyle \displaystyle \begin{aligned}\sum_{k=0}^{n}{n\choose k}F(k) &=\frac{1}{\sqrt{5}}\sum_{k=0}^{n}{n\choose k}\left(\varphi^k-\left(1-\varphi\right)^k\right)\\ &= \frac{1}{\sqrt{5}}\left[\sum_{k=0}^{n}{n\choose k}\varphi^k-\sum_{k=0}^{n}{n\choose k}\left(1-\varphi\right)^k\right]\\ &= \frac{1}{\sqrt{5}}\left[\left(1+\varphi\right)^n-\left(2-\varphi\right)^n\right]\end{aligned}

That said, a quick check shows that $\displaystyle \varphi^2=1+\varphi$ and $\displaystyle \displaystyle \left(1-\varphi\right)^2=1-2\varphi+\varphi^2=1-\varphi+(\varphi^2-\varphi)=1-\varphi+1=2-\varphi$. So that the above shows

\displaystyle \displaystyle \begin{aligned}\sum_{k=0}^{n}{n\choose k}F(k) &= \frac{1}{\sqrt{5}}\left[\left(1+\varphi\right)^n-\left(2-\varphi\right)^n\right]\\ &= \frac{1}{\sqrt{5}}\left[\left(\varphi^2\right)^n-\left(\left(1-\varphi\right)^2\right)^n\right]\\ &= \frac{1}{\sqrt{5}}\left[\varphi^{2n}-\left(1-\varphi\right)^{2n}\right]\\ &= F(2n)\end{aligned}

3. A couple more proofs here.

A more general form would be: $\displaystyle f_{n\cdot m} = \sum_{k=0}^n{\binom{n}{k}\cdot f_k \cdot f_m^k\cdot f^{n-k}_{m-1}}$ ( setting $\displaystyle m = 2$ you get the particular case above).