Fibonacci Proof II

**veronicak5678** · February 4th 2011, 06:00 PM

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

**Drexel28** · February 4th 2011, 10:57 PM

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

**PaulRS** · February 16th 2011, 03:04 AM

A couple more proofs here.

A more general form would be: $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 $m = 2$ you get the particular case above).

Thread: Fibonacci Proof II

LinkBack

Thread Tools

Display

Fibonacci Proof II

Similar Math Help Forum Discussions

Fibonacci Proof

Need help on Fibonacci proof

Fibonacci proof

Fibonacci proof

another fibonacci proof

Search Tags