Results 1 to 10 of 10

Math Help - Help with induction for Fibonacci Numbers

  1. #1
    Newbie
    Joined
    Apr 2007
    Posts
    2

    Help with induction for Fibonacci Numbers

    Can anyone please help? I don't know if I am doing it right. I am stuck in the inductive step.

    Using induction please prove the following formula:

    u2 + 2 u4 + 3u6 +...+ n u2n = n u(2n+1) - u2n

    where the numbers to the the right of the letter u are subscripts.


    So far I proved

    Base Case: n = 1

    LHS: 1 *u2(1) = 1*u2 = 1*1 =1
    RHS: 1* u(2(1)+1) - u2(1) = 1*u3 -u2 = u3-u2 = 2-1 =1

    I.H.= Assume for all n to be true
    u2 + 2 u4 + 3u6 +... + n u2n = n u(2n+1) - u2n

    I.S. Prove for n+1

    u2 +2 u4+3 u6+.. +n u2n + (n+1) u2(n+1) = (n+1) u(2(n+1)+1) - u2(n+1)

    By I.H. then,

    n u(2n+1) - U2n + (n+1) u2(n+1)

    and then I get stuck....
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by Beginner_gurl View Post
    Using induction please prove the following formula:

    u2 + 2 u4 + 3u6 +...+ n u2n = n u(2n+1) - u2n

    ...

    I.H.= Assume for all n to be true
    u2 + 2 u4 + 3u6 +... + n u2n = n u(2n+1) - u2n

    I.S. Prove for n+1

    u2 +2 u4+3 u6+.. +n u2n + (n+1) u2(n+1) = (n+1) u(2(n+1)+1) - u2(n+1)

    By I.H. then,

    n u(2n+1) - U2n + (n+1) u2(n+1)
    n*u_{2n+1} - u_{2n} + (n + 1)*u_{2(n+1)} = (n + 1)*u_{2(n+1)+1} - u_{2(n+1)}

    Rewriting and rearanging these terms, we get:
    n(u_{2n+1} + u_{2n+2}) + u_{2n+2} - u_{2n} = nu_{2n+3} + u_{2n+3} - u_{2n+2}

    Now we need to try to break these up:

    Recall that u_{k} + u_{k+1} = u_{k+2}, we will use this to rewrite many of the above Fibonacci Numbers.

    n(u_{2n+1} + u_{2n+2}) + u_{2n+2} - u_{2n} = nu_{2n+3} + u_{2n+3} - u_{2n+2}
    nu_{2n+3} + u_{2n+1} + u_{2n} - u_{2n} = nu_{2n+3} + u_{2n+1} + u_{2n+2} - u_{2n+2}
    nu_{2n+3} + u_{2n+1} = nu_{2n+3} + u_{2n+1}

    Q.E.D.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Rebesques's Avatar
    Joined
    Jul 2005
    From
    At my house.
    Posts
    538
    Thanks
    11
    Recall that u_{k} + u_{k+1} = u_{k+2}
    How do you prove something like this, without running intio the same kind of trouble Gurl did?

    For Fibonacci numbers, and generally recursive sequences, you should use the transfinite induction scheme:

    a) Prove for the first term.
    b) Suppose true for all terms up to n>1.
    c) Prove for n.

    Good luck!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,706
    Thanks
    625
    Hello, Beginner_gurl!

    This is a wicked one . . . I had to do Olympic-level gymnastics.


    Using induction prove the following formula:

    . . F
    2 + 2F4 + 3F6 + ... + nF2n .= .nF2n+1 - F2n

    You've already established the Base Case: S
    1.

    Assume S
    k: .F2 + 2F4 + 3F6 + ... + kF2k .= .kF2k+1 - F2k


    Add (k+1)F
    2k+2 to both sides:

    . . F
    2 + 2F4 + 3F6 + ... + kF2k + (k+1)F2k+2 .= .kF2k+1 - F2k + (k+1)F2k+2

    The left side is the LHS of S
    k+1.

    We must show that the right side equals the RHS of S
    k+1: .(k+1)F2k+3 - F2k+2


    The right side is: .kF
    2k+1 - F2k + (k+1)F2k+2 .= .kF2k+1 - F2k + kF2k+2 + F2k+2

    Add and subtract F
    2n+1: .kF2k+1 - F2k + kF2k+2 + F2k+2 + F2k+1 - F2k+1

    We have: .kF
    2k+1 + kF2k+2 + F2k+1 + F2k+2 - F2k - F2k+1

    Factor: .k(F
    2k+1 + F2k+2) + (F2k+1 + F2k+2) - (F2k + F2k+1)
    . . . . . . . .\_________/ . - . \_________/ . - .\_______/
    . . . . . . . .
    This is F2k+3 . . . . . This is F2k+3 . . . .This is F2k+2

    Then we have: .kF
    2k+3 + F2k+3 - F2k+2

    And therefore: . (k+1)F
    2k+3 - F2k+2 . . . . . There!


    . . Kids, don't try this at home . . .

    Edit: corrected the goof . . . thanks, ec!
    Last edited by Soroban; April 23rd 2007 at 06:48 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2007
    Posts
    2

    Thanks

    I see the light................................thank you!!!!!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by Rebesques View Post
    How do you prove something like this, without running intio the same kind of trouble Gurl did?

    For Fibonacci numbers, and generally recursive sequences, you should use the transfinite induction scheme:

    a) Prove for the first term.
    b) Suppose true for all terms up to n>1.
    c) Prove for n.

    Good luck!
    This doesn't have to be proven. The Fibonacci Numbers are defined in this way.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by Soroban View Post
    Hello, Beginner_gurl!

    This is a wicked one . . . I had to do Olympic-level gymnastics.



    You've already established the Base Case: S
    1.

    Assume S
    k: .F2 + 2F4 + 3F6 + ... + kF2k .= .kF2k+1 - F2k


    Add (k+1)F
    2k+2 to both sides:

    . . F
    2 + 2F4 + 3F6 + ... + kF2k + (k+1)F2k+2 .= .kF2k+1 - F2k + (k+1)F2k+2

    The left side is the LHS of S
    k+1.

    We must show that the right side equals the RHS of S
    k+1: .(k+1)F2k+3 - F2k+2


    The right side is: .kF
    2k+1 - F2k + (k+1)F2k+2 .= .kF2k+1 - F2k + kF2k+2 + F2k+2

    Add and subtract F
    2n+1: .kF2k+1 - F2k + kF2k+2 + F2k+2 + F2k+1 - F2k+1

    We have: .kF
    2k+1 + kF2k+2 + F2k+1 + F2k+2 - F2k - F2k+1

    Factor: .k(F
    2k+1 + F2k+2) + (F2k+1 + F2k+2) - (F2k + F2k+1)
    . . . . . . . .\_________/ . - . \_________/ . - .\_______/
    . . . . . . . .
    This is F2k+3 . . . . . This is F2k+3 . . . .This is F2k+2

    Then we have: .kF
    2k+2 + F2k+3 - F2k+2

    And therefore: . (k+1)F
    2k+3 - F2k+2 . . . . . There!


    . . Kids, don't try this at home . . .
    I go through all the work of proving it and you come along and make it look more pretty.

    Good job once again.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by Soroban View Post

    Then we have: .kF
    2k+2 + F2k+3 - F2k+2

    And therefore: . (k+1)F
    2k+3 - F2k+2 . . . . . There!
    There's a slight typo!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Rebesques's Avatar
    Joined
    Jul 2005
    From
    At my house.
    Posts
    538
    Thanks
    11
    The Fibonacci Numbers are defined in this way.
    Yeap! So its ok.

    ps. Is it easier to solve with the trans-induction? Or am I making things difficult?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ecMathGeek View Post
    I go through all the work of proving it and you come along and make it look more pretty.

    Good job once again.
    Don't you hate it when he does that. Soroban has some technique of finding the simplest, prettiest way to do a problem, and then he tops it off with his formatting skills that don't even require LaTex.

    It's all good though. Seeing him solve stuff gives me ideas to solve other stuff
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] induction problem with fibonacci numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 5th 2011, 09:00 PM
  2. Strong induction on Fibonacci numbers
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 27th 2010, 11:00 AM
  3. Fibonacci numbers pattern--induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 8th 2009, 01:56 PM
  4. Induction with Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 5th 2009, 09:00 AM
  5. Induction and Fibonacci Numbers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 5th 2009, 08:42 AM

Search Tags


/mathhelpforum @mathhelpforum