Results 1 to 5 of 5

Math Help - Fibonacci numbers pattern--induction

  1. #1
    Junior Member
    Joined
    Aug 2008
    Posts
    44

    Fibonacci numbers pattern--induction

    Prove that the sum of the first n Fibonacci numbers is equal to the (n+2)nd fibonacci number minus one.

    Base case: n=1
    1st Fib# =1 =third fib# -1=2-1 True

    This is where I have problems.

    f_{1}+f_{2}+f_{3}+....+f_{n}+f_{n+1}

    =f_{n+2}-1+f_{n+1}

    after this I have no idea how to proceed.
    Last edited by yzc717; September 7th 2009 at 04:34 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Here's a simple proof.

    f_{1}+f_{2}+f_{3}+.....+f_{n}

    =(f_{3}-f_{2})+(f_{4}-f_{3})+(f_{5}-f_{4})+....+(f_{n+2}-f_{n+1})

    =f_{n+2}-f_{2}

    f_{n+2}-1

    QED

    If you want to try induction, try f_{1}+f_{2}+f_{3}+....+f_{n}+f_{n+1}

    =(f_{3}-f_{2})+(f_{4}-f_{3})+(f_{5}-f_{4})+....+(f_{n+2}-f_{n+1})+(f_{n+3}-f_{n+2})

    =f_{n+3}-f_{n+1}-f_{2}

    And so on......
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2008
    Posts
    44
    Quote Originally Posted by galactus View Post

    =(f_{3}-f_{2})+(f_{4}-f_{3})+(f_{5}-f_{4})+....+(f_{n+2}-f_{n+1})+(f_{n+3}-f_{n+2})

    =f_{n+3}-f_{n+1}-f_{2}

    And so on......
    I still don't get these.

    This is where I have problems.

    f_{1}+f_{2}+f_{3}+....+f_{n}+f_{n+1}

    =f_{n+2}-1+f_{n+1}

    after this I have no idea how to proceed.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    That's because f_{2}=1 and it is a telescoping series so everything cancels except those terms.

    Note that f_{n+3}-f_{n+1}=f_{n+2}

    So, we have f_{n+2}-1, as before, when using induction.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by yzc717 View Post
    Prove that the sum of the first n Fibonacci numbers is equal to the (n+2)nd fibonacci number minus one.

    Base case: n=1
    1st Fib# =1 =third fib# -1=2-1 True

    This is where I have problems.

    f_{1}+f_{2}+f_{3}+....+f_{n}+f_{n+1}

    =f_{n+2}-1+f_{n+1}

    after this I have no idea how to proceed.
    You are almost done.

    =f_{n+2}-1+f_{n+1} = f_{n+3}-1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction Proof- Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 18th 2010, 06:28 AM
  2. Induction with Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 5th 2009, 09:00 AM
  3. Induction and Fibonacci Numbers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 5th 2009, 08:42 AM
  4. Help with induction for Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: April 23rd 2007, 07:37 AM
  5. Help describing pattern (Fibonacci Numbers)
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 26th 2007, 04:00 AM

Search Tags


/mathhelpforum @mathhelpforum