# Fibonacci Proof

• Dec 2nd 2008, 12:34 PM
Kiwi_Dave
Fibonacci Proof
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!
• Dec 2nd 2008, 02:54 PM
PaulRS
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.
• Dec 2nd 2008, 05:12 PM
PaulRS
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}$