Homework Help: Help with induction

1. Aug 28, 2010

remaan

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.

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. Aug 28, 2010

n.karthick

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.

3. Aug 28, 2010

remaan

Re: Help with induction !!

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

4. Aug 28, 2010

annoymage

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

5. Aug 28, 2010

remaan

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

6. Aug 28, 2010

annoymage

Re: Help with induction !!

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

7. Aug 28, 2010

remaan

Re: Help with induction !!

and we can replace the a by n right ?

8. Aug 28, 2010

annoymage

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

9. Aug 28, 2010

remaan

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

10. Aug 28, 2010

remaan

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 ?

11. Aug 28, 2010

annoymage

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

12. Aug 28, 2010

remaan

Re: Help with induction !!

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

13. Aug 28, 2010

remaan

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 ?

14. Aug 28, 2010

remaan

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 ?

15. Aug 28, 2010

annoymage

Re: Help with induction !!

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: Aug 28, 2010
16. Sep 1, 2010

remaan

Re: Help with induction !!

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