Results 1 to 5 of 5

Thread: 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.

    $\displaystyle f_{1}+f_{2}+f_{3}+....+f_{n}+f_{n+1}$

    $\displaystyle =f_{n+2}-1+f_{n+1}$

    after this I have no idea how to proceed.
    Last edited by yzc717; Sep 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,002
    Thanks
    1
    Here's a simple proof.

    $\displaystyle f_{1}+f_{2}+f_{3}+.....+f_{n}$

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

    $\displaystyle =f_{n+2}-f_{2}$

    $\displaystyle f_{n+2}-1$

    QED

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

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

    $\displaystyle =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

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

    $\displaystyle =f_{n+3}-f_{n+1}-f_{2}$

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

    This is where I have problems.

    $\displaystyle f_{1}+f_{2}+f_{3}+....+f_{n}+f_{n+1}$

    $\displaystyle =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,002
    Thanks
    1
    That's because $\displaystyle f_{2}=1$ and it is a telescoping series so everything cancels except those terms.

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

    So, we have $\displaystyle 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.

    $\displaystyle f_{1}+f_{2}+f_{3}+....+f_{n}+f_{n+1}$

    $\displaystyle =f_{n+2}-1+f_{n+1}$

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

    $\displaystyle =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: Feb 18th 2010, 06:28 AM
  2. Induction with Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Jan 5th 2009, 09:00 AM
  3. Induction and Fibonacci Numbers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Jan 5th 2009, 08:42 AM
  4. Help with induction for Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: Apr 23rd 2007, 07:37 AM
  5. Help describing pattern (Fibonacci Numbers)
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Mar 26th 2007, 04:00 AM

Search Tags


/mathhelpforum @mathhelpforum