Results 1 to 3 of 3

Math Help - Fibonacci Proof

  1. #1
    Member
    Joined
    May 2008
    From
    Melbourne Australia
    Posts
    210
    Thanks
    25

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Consider: <br />
F = \left( {\begin{array}{*{20}c}<br />
   1 & 1  \\<br />
   1 & 0  \\<br /> <br />
 \end{array} } \right) \Rightarrow F^n  = \left( {\begin{array}{*{20}c}<br />
   {f_{n + 1} } & {f_n }  \\<br />
   {f_n } & {f_{n - 1} }  \\<br /> <br />
 \end{array} } \right)<br />
(1)

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

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

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

    Now see the entries on the LHS by using (1) and we are done.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Okay, now a combinatorial proof.

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

    Now the RHS of your identity equals <br />
\left| {A_{2n-1} } \right| <br />

    First note that, if a vector <br />
\left( {a_1 ,...,a_r } \right):r \ge 0{\text{ with }}a_i  = 1{\text{ or }}a_i  = 2 satisfies <br />
\sum {a_i }  = 2n - 1<br />
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: <br />
\left( {a_1 ,...,a_n ,a_{n + 1} ,...,a_{n + r} } \right)<br />
( 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 <br />
a_{n + 1}  + ... + a_{n + r}  = n - 1 - k<br />
. but this can be done in exactly: <br />
\left| {A_{n - 1 - k} } \right| = f_{n - k} <br />
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}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 5th 2011, 02:47 AM
  2. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 28th 2009, 10:21 PM
  3. Need help on Fibonacci proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 23rd 2009, 08:31 AM
  4. Fibonacci proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 26th 2007, 07:37 AM
  5. another fibonacci proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 16th 2007, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum