1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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