1. ## Fibonacci Proof

Prove that:

$\displaystyle \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:

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

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

The relation holds for n=1 so proceeding by induction:
$\displaystyle 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)}$

$\displaystyle \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:

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

and

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

Of course I could be on completely the wrong track!

2. Consider: $\displaystyle 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: $\displaystyle \left( {F + {\text{Id}}} \right)^n = \sum\limits_{k = 0}^n {\binom{n}{k}\cdot F^k }$ since $\displaystyle F$ commutes with the identity. ( we define $\displaystyle F^0 = {\text{Id}}$ )

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

Thus: $\displaystyle \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.

3. Okay, now a combinatorial proof.

Consider: $\displaystyle 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 $\displaystyle \left| {A_n } \right| = f_{n + 1}$ (check the initial values and the recurrence relation)

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

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

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

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