Results 1 to 4 of 4

Math Help - Induction and Fibonacci Numbers

  1. #1
    Banned
    Joined
    Jan 2009
    Posts
    27

    Smile Induction and Fibonacci Numbers

    I am trying to figure out how to show that f_{n+1}f_{n-1}-f_{n}^{2}=(-1)^{n} when n is a positive integer.

    My Work
    P(n) is f_{n+1}f_{n-1}-f_{n}^{2}=(-1)^n for n>=1

    Basis step - P(1) is true because f_{2}f_{0}-f_{1}^{2}=1*0-1=-1=(-1)^1
    Inductive step - Assume P(k)=f_{k+1}f_{k-1}-f_{k}^{2}=(-1)^k is true,
    then P(k+1)=f_{k+2}f_{k}-(f_{k+1}^2=(-1)^{k+1} is true

    Then prove P(k+1)=[f_{k+1}f_{k-1}-f_{k}^{2}]+[f_{k+2}f_{k}-f_{k+1}^{2}]=(-1)^k+[f_{k+2}f_{k}-f_{k+1}^2], but I can't figure out how to get this P(k+1) equation to equal (-1)^{k+1}

    I received the reply below, which is probably a wonderful answer, but I am unclear as to where in the 3rd line came from. I though you had to add the initial part of the P(k+1) equation, which is f_{k+1}f_{k}-f_{k+1}^2, to both sides of the P(k) equation as I did above.

    First Reply
    Assume for n.

    We want to show that





    ,<--- negative of the induction hypothesis

    by the induction hypothesis.



    So, is true.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2008
    From
    Montreal, Canada
    Posts
    7
    f_n(f_{n+1}+f_n) - f_{n+1}(f_{n}+f_{n-1}) comes directly from the definition of the Fibonacci numbers. Remember that f_n  =  f_{n-1} + f_{n-2}?
    So in your case in f_{n}f_{n+2}  - f^2_{n+1}
    f_{n+2} = f_{n+1}+f_{n}
    and
    f^2_{n+1} = f_{n+1}f_{n+1} = f_{n+1}(f_{n}+f_{n-1}) ,
    since f_{n+1}  =  f_{n} + f_{n-1}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Jan 2009
    Posts
    27

    Question

    The math makes sense but I still do not understand why you are allowed to do the "negative of the inductive hypothesis" to get the extra -1 to make the answer {-1}^{K}. Doesn't the answer also still need to be {-1}^{K+1}?

    Also, I thought it wasn't supposed to prove the exact P(k+1) equation in the inductive step but rather the P(k) equation with the first part of P(k+1) added to both sides as follows:



    Then, aren't I supposed to work on the second half of this equation to make it equal {-1}^{K+1}?


    EDIT:

    The math makes sense but I still do not understand why you are allowed to do the "negative of the inductive hypothesis" to get the extra -1 to make the answer be ? I already understand that - {-1}^{k}={-1}^{k+1} I just don't know where the exra -1 came from.
    Last edited by mr fantastic; January 5th 2009 at 06:07 AM. Reason: Merge
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2008
    From
    Montreal, Canada
    Posts
    7
    First of all
    (-1)^k \not= (-1)^{k+1}
    because they have opposite signs.

    Second of all, extra -1 comes from swapping terms in the equation of the inductive assumption, as in 5-2=3, but 2-5=-(3). That's it.
    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. Help with induction for Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: April 23rd 2007, 07:37 AM

Search Tags


/mathhelpforum @mathhelpforum