Results 1 to 7 of 7

Math Help - Induction with Fibonacci Numbers

  1. #1
    Banned
    Joined
    Jan 2009
    Posts
    27

    Red face Induction with 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_2f_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

    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]

    I can't figure out how to get this equation to equal (-1)^(k+1)
    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
    Assume f_{n-1}f_{n+1}-f_{n}^{2}=(-1)^{n} for n.

    We want to show that f_{n}f_{n+2}-f_{n+1}^{2}=(-1)^{n+1}

    =f_{n}(f_{n+1}+f_{n})-f_{n+1}(f_{n}+f_{n-1})

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

    =f_{n}^{2}-f_{n+1}f_{n-1} \;\  =  \;\ -(-1)^n,<--- negative of the induction hypothesis

    =-(-1)^{n}=(-1)^{n+1} by the induction hypothesis.

    \therefore, \;\ f_{n}f_{n+2}-f_{n+1}^{2}=-(-1)^{n}

    So, f_{n-1}f_{n+1}-f_{n}^{2}=(-1)^{n} is true.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Jan 2009
    Posts
    27

    Thank you!

    I am having such a hard time with this problem but you definitely opened up my eyes to a totally new approach. Thank you sooo much. I understand all the math but I am not totally sure where you came up with the following:



    I'm sure its obvious, I have just gotten myself so confused. Do you add the k+1 equation f_(k+1)f_(k-1)-(f_k)^2
    to both sides of ? I was trying to teach myself by looking at examples but it doesn't seem to be working out.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jan 2007
    Posts
    42
    Quote Originally Posted by calabrone View Post
    I am having such a hard time with this problem but you definitely opened up my eyes to a totally new approach. Thank you sooo much. I understand all the math but I am not totally sure where you came up with the following:



    I'm sure its obvious, I have just gotten myself so confused. Do you add the k+1 equation f_(k+1)f_(k-1)-(f_k)^2
    to both sides of ? I was trying to teach myself by looking at examples but it doesn't seem to be working out.
    --------------
    definition of fibonacci sequence

    f(n+2) = f(n) +f(n+1)

    and one of the f(n)'s in the second term with
    with f(n) = f(n-1) +f(n)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Jan 2009
    Posts
    27

    My Work So Far With Your Help

    I am trying to get the following equation to equal {-1}^{k+1}

    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}]

    Steps
    P(k+1)={-1}^{k}+[f_{k+2}f_{k}-f_{k+1}^{2}]
    ={-1}^{k}+(f_{k}+f_{k+1})f_{k}-(f_{k-1}+f_{k})f_{k+1}
    ={-1}^{k}+f_{k}^{2}+f_{k}f_{k+1}-f_{k-1}f_{k+1}-f_{k}f_{k+1}
    ={-1}^{k}+f_{k}^2-f_{k+1}f_{k-1}
     <br />
={-1}^{k}+f_{k}(f_{k-1}+f_{k-2})-(f_{k}+f_{k-1})f_{k-1}<br />
     <br />
={-1}^{k}+f_{k}f_{k-1}+f_{k}f_{k-2}-f_{k}f_{k-1}-f_{k-1}f_{k-1}<br />
     <br />
={-1}^{k}+f_{k}f_{k-2}-f_{k-1}f_{k-1}<br />
     <br />
={-1}^{k}<br />

    Does anyone know how to get the extra -1 to turn {-1}^{k} into {-1}^{k+1}?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Look my my post. Perhaps it is hard to see. But, the negative of the induction hypothesis is -(-1)^{k}=-1(-1)^{k}=(-1)^{k+1}.

    See?.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Jan 2009
    Posts
    27

    Talking Now I understand that part

    Thank you! I'm concentrating so hard that I'm missing the obvious!

    You simply switched the terms around to get an extra negative on the right side of the equation? and you simplified the P(k+1) equation which made it the negative of the P(k) equation, correct?

    Also, am I incorrect to think you have to make the following equation equal , not just the f_{k+2}f_{k}-f_{k+1}^{2}={-1}^{k}?:

    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 and Fibonacci Numbers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 5th 2009, 08:42 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