Fibonacci Proof II

Quote:

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 \varphi=\frac{1+\sqrt{5}}{2}$ , then a common fact (Binet's formula) says that $\displaystyle F_n=\frac{\varphi^n-\left(1-\varphi\right)^n}{\sqrt{5}}$ . Thus,

$\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 $\varphi^2=1+\varphi$ and $\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 \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}$