Results 1 to 3 of 3

Math Help - Fibonacci Proof II

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    225

    Fibonacci Proof II

    (n choose 0)*F(0) + (n choose 1)*F(1) + ... + (n choose n)*F(n)=F(2n)
    I'm beginning to think induction is a bad approach...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by veronicak5678 View Post
    (n choose 0)*F(0) + (n choose 1)*F(1) + ... + (n choose n)*F(n)=F(2n)
    I'm beginning to think induction is a bad approach...
    Let \displaystyle \varphi=\frac{1+\sqrt{5}}{2}, then a common fact (Binet's formula) says that \displaystyle F_n=\frac{\varphi^n-\left(1-\varphi\right)^n}{\sqrt{5}}. Thus,


    \displaystyle \begin{aligned}\sum_{k=0}^{n}{n\choose k}F(k) &=\frac{1}{\sqrt{5}}\sum_{k=0}^{n}{n\choose k}\left(\varphi^k-\left(1-\varphi\right)^k\right)\\ &= \frac{1}{\sqrt{5}}\left[\sum_{k=0}^{n}{n\choose k}\varphi^k-\sum_{k=0}^{n}{n\choose k}\left(1-\varphi\right)^k\right]\\ &= \frac{1}{\sqrt{5}}\left[\left(1+\varphi\right)^n-\left(2-\varphi\right)^n\right]\end{aligned}


    That said, a quick check shows that \varphi^2=1+\varphi and \displaystyle \left(1-\varphi\right)^2=1-2\varphi+\varphi^2=1-\varphi+(\varphi^2-\varphi)=1-\varphi+1=2-\varphi. So that the above shows


    \displaystyle \begin{aligned}\sum_{k=0}^{n}{n\choose k}F(k) &= \frac{1}{\sqrt{5}}\left[\left(1+\varphi\right)^n-\left(2-\varphi\right)^n\right]\\ &= \frac{1}{\sqrt{5}}\left[\left(\varphi^2\right)^n-\left(\left(1-\varphi\right)^2\right)^n\right]\\ &= \frac{1}{\sqrt{5}}\left[\varphi^{2n}-\left(1-\varphi\right)^{2n}\right]\\ &= F(2n)\end{aligned}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    A couple more proofs here.

    A more general form would be: f_{n\cdot m} = \sum_{k=0}^n{\binom{n}{k}\cdot f_k \cdot f_m^k\cdot f^{n-k}_{m-1}} ( setting m = 2 you get the particular case above).
    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, 03:47 AM
  2. Need help on Fibonacci proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 23rd 2009, 09:31 AM
  3. Fibonacci proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 26th 2007, 08:37 AM
  4. Fibonacci proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 16th 2007, 08:36 AM
  5. another fibonacci proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 16th 2007, 08:10 AM

Search Tags


/mathhelpforum @mathhelpforum