How do we use induction to prove the Fibonacci numbers satisfy this formula?

  • Thread starter Thread starter remaan
  • Start date Start date
  • Tags Tags
    Induction
remaan
Messages
132
Reaction score
0
Help with induction !

Homework Statement




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



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
 
Physics news on Phys.org


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.
 


Ya - but then how am I going to use induction ?
If I only did what you suggested ?
 


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
 


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
 


hmm, Fibonacci sequence is given by Fa=Fa-1+Fa-2
 


and we can replace the a by n right ?
 


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
 


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
 
  • #10


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 ?
 
  • #11


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
 
  • #12


oky Now I see what you mean,
But still working the Algerbra for the manipulation
 
  • #13


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 ?
 
  • #14


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 ?
 
  • #15


hmm, here's the clue ;P F_{n+1}=F_n+F_{n-1} \Rightarrow F_n-F_{n+1}=-F_{n-1}
 
Last edited:
  • #16


Thanks a lot -
I am now done with this problem :)
 
Back
Top