Fibonacci Proof

**Kiwi_Dave** · December 2nd 2008, 12:34 PM

Prove that:

$\binom n1F_1+\binom n2F_2+\binom n3F_3+...+\binom n{n-1}F_{n-1}+F_n=f_{2n}$

OK So I gave it a go as follows:

$\binom nnF_n=F_n$ and $\binom n{n+a}F_{n+a}=0$ (a>0)

So the problem is equivalent to, prove:
$\binom n1F_1+\binom n2F_2+\binom n3F_3+...=f_{2n}$

The relation holds for n=1 so proceeding by induction:
$F_{2(n+1)}=F_{2n}+F_{2n+1}=2F_{2n}+F_{2n-1}=3F_{2n}-F_{2n-2}=3F_{2n}-F_{2(n-1)}$

$\therefore F_{2(n+1)}=3\binom n1F_1-\binom {n-1}1F_1+3\binom n2F_2-\binom {n-1}2F_2+3\binom n3F_3-\binom {n-1}3F_3+...$

Unfortunately I have been unable to manipulate this to give the required result. I expect to use the two relations:

$\binom nr=\binom {n-1}r+\binom {n-1}{r-1}$

and

$F_{n+1}=F_n+F_{n-1}$

Of course I could be on completely the wrong track!

**PaulRS** · December 2nd 2008, 02:54 PM

Consider: $ F = \left( {\begin{array}{*{20}c} 1 & 1 \\ 1 & 0 \\ \end{array} } \right) \Rightarrow F^n = \left( {\begin{array}{*{20}c} {f_{n + 1} } & {f_n } \\ {f_n } & {f_{n - 1} } \\ \end{array} } \right) $ (1)

We also have: $ \left( {F + {\text{Id}}} \right)^n = \sum\limits_{k = 0}^n {\binom{n}{k}\cdot F^k } $ since $F$ commutes with the identity. ( we define $ F^0 = {\text{Id}} $ )

However, note that: $ F + {\text{Id}} = \left( {\begin{array}{*{20}c} 2 & 1 \\ 1 & 1 \\ \end{array} } \right) = F^2 $

Thus: $ \sum\limits_{k = 0}^n {\binom{n}{k} \cdot F^k } = F^{2n} = \left( {\begin{array}{*{20}c} {f_{2n + 1} } & {f_{2n} } \\ {f_{2n} } & {f_{2n - 1} } \\ \end{array} } \right) $

Now see the entries on the LHS by using (1) and we are done.

**PaulRS** · December 2nd 2008, 05:12 PM

Okay, now a combinatorial proof.

Consider: $ A_n = \left\{ {\left( {a_1 ,...,a_r } \right):r \ge 0{\text{ with }}a_i = 1{\text{ or }}a_i = 2{\text{ such that }}\sum {a_i } = n} \right\} $ note that $ \left| {A_n } \right| = f_{n + 1} $ (check the initial values and the recurrence relation)

Now the RHS of your identity equals $ \left| {A_{2n-1} } \right| $

First note that, if a vector $ \left( {a_1 ,...,a_r } \right):r \ge 0{\text{ with }}a_i = 1{\text{ or }}a_i = 2$ satisfies $ \sum {a_i } = 2n - 1 $ then $r\geq{n}$ ( indeed, at most we can have n-1 2s ) (1)

So it is formed by combining a vector of $n$ entries, and a complementary one, like this: $ \left( {a_1 ,...,a_n ,a_{n + 1} ,...,a_{n + r} } \right) $ ( $r$ can be 0, $a_i=1$ or $a_i=2$ )

Now choose $k$ of the first $n$ entries to be 2s, the rest of the first n entries are going to be defined as 1s. We can do this in $\binom{n}{k}$ ways. And we have summed $2k+(n-k)=k+n$ so far. So we require $ a_{n + 1} + ... + a_{n + r} = n - 1 - k $ . but this can be done in exactly: $ \left| {A_{n - 1 - k} } \right| = f_{n - k} $ ways. So if, among the first n entries, we have $k$ 2s, we can achieve this in $\binom{n}{k}\cdot{f_{n - k} }$ ways.

If we sum all the possible number of 2s among the first n entries ( disjoint cases) we'll have: $\sum_{k=0}^{n}\binom{n}{k}\cdot{f_{n - k} }=f_{2n}$

Thread: Fibonacci Proof

LinkBack

Thread Tools

Display

Fibonacci Proof

Similar Math Help Forum Discussions

Fibonacci Proof

Fibonacci Proof

Need help on Fibonacci proof

Fibonacci proof

another fibonacci proof

Search Tags