Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Help with induction

  1. Aug 28, 2010 #1
    Help with induction !!

    1. The problem statement, all variables and given/known data


    Prove that for all n  1, the Fibonacci numbers satisfy
    Fn-1 Fn+1 - (Fn)2 = (-1)n:



    3. The attempt at a solution
    I understand that we have to use induction to prove this.
    And we start with a base case of n = 1

    But, how do we plug the numbers in the formula above ?
    I mean what is F ?
    Is there any other givens we should know ?

    Am I in the right direction
     
  2. jcsd
  3. Aug 28, 2010 #2
    Re: Help with induction !!

    F is the Fibonacci number as given below
    F0=0
    F1=1
    F2=1
    F3=2
    F4=3
    F5=5
    and so on.

    Plug in the values of F for any n and see that the relation given to you holds.
     
  4. Aug 28, 2010 #3
    Re: Help with induction !!

    Ya - but then how am I going to use induction ?
    If I only did what you suggested ???
     
  5. Aug 28, 2010 #4
    Re: Help with induction !!

    so, if n=1, it satisfied, assume its true for some n>=1

    maybe easiest way to prove from (-1)n+1=-(-1)n

    and try to show Fn Fn+2 - (Fn+1)2
     
  6. Aug 28, 2010 #5
    Re: Help with induction !!

    Yes, this is exactly where I got stuck !!!

    I need to show that the formula you've written is the same as the one given in the problem, using the inductive Hypothesis.

    To do that : I need to show that each of the corresonding terms are eaqual (to get the over all equality of the eqution)

    Fn Fn+1 should be equal Fn-1 Fn+1

    and F(n)^2 should be equal to F(n+1)^2


    Can you Please give me a hint to continue ?

    i was thinking about multiplying the equation by some element/number to get red of the numbers and reach the original one ?

    What do you think ???

    remaan
     
  7. Aug 28, 2010 #6
    Re: Help with induction !!

    hmm, Fibonacci sequence is given by Fa=Fa-1+Fa-2
     
  8. Aug 28, 2010 #7
    Re: Help with induction !!

    and we can replace the a by n right ?
     
  9. Aug 28, 2010 #8
    Re: Help with induction !!

    of course because its true for all a>=2, so -(Fn-1 Fn+1 - (Fn)2) and try to manipulate to get Fn Fn+2 - (Fn+1)2
     
  10. Aug 28, 2010 #9
    Re: Help with induction !!

    Thanks annoymage -
    you're doing a good job making me progress with this -

    I will do that and let you know what happens with me
     
  11. Aug 28, 2010 #10
    Re: Help with induction !!

    But, isn't it the other way around : I meaning shouldn't I start with
    Fn Fn+2 - (Fn+1)2

    and manipulate it to get : -(Fn-1 Fn+1 - (Fn)2)

    Because, this is how standard induction works.

    Or, it doesn't really matters ?
     
  12. Aug 28, 2010 #11
    Re: Help with induction !!

    its the same thing you want to prove (-1)n+1=Fn Fn+2 - (Fn+1)2

    so if you start with (-1)n+1, then show (-1)n+1=-(-1)n= -(Fn-1 Fn+1 - (Fn)2)=.......=Fn Fn+2 - (Fn+1)2

    if you start with Fn Fn+2 - (Fn+1)2, then show Fn Fn+2 - (Fn+1)2=.....=-(Fn-1 Fn+1 - (Fn)2)==-(-1)n=(-1)n+1
     
  13. Aug 28, 2010 #12
    Re: Help with induction !!

    oky Now I see what you mean,
    But still working the Algerbra for the manipulation
     
  14. Aug 28, 2010 #13
    Re: Help with induction !!

    Now, I am trying to use the three equations to get to -(-1)^n+1

    However, I not sure that I am in the right direction.

    I am trying to replace Fn with its value from the formula you stated, and the same for Fn+2 and Fn+1

    Do you think I should continue with that ?
     
  15. Aug 28, 2010 #14
    Re: Help with induction !!

    Greetings,
    So the final thing I got is :
    (Fn)^2 + Fn+1 (Fn - Fn+1)

    Now how to precede to get what you've mentioned ?
     
  16. Aug 28, 2010 #15
    Re: Help with induction !!

    hmm, here's the clue ;P [tex]F_{n+1}=F_n+F_{n-1} \Rightarrow F_n-F_{n+1}=-F_{n-1}[/tex]
     
    Last edited: Aug 28, 2010
  17. Sep 1, 2010 #16
    Re: Help with induction !!

    Thanks a lot -
    I am now done with this problem :)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook