Results 1 to 3 of 3

Thread: Fibonacci Proof

  1. #1
    Member
    Joined
    May 2008
    From
    Melbourne Australia
    Posts
    217
    Thanks
    29

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

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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.
    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: $\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}$
    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: Feb 5th 2011, 02:47 AM
  2. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Nov 28th 2009, 10:21 PM
  3. Need help on Fibonacci proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 23rd 2009, 08:31 AM
  4. Fibonacci proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 26th 2007, 07:37 AM
  5. another fibonacci proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 16th 2007, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum