Proof by Induction

  • #1

Homework Statement


The fibonacci numbers are defined by F0 = 0 F1 = 1 and Fn = n-1 + Fn-2 for n >= 2.
Use induction the prove the following:
Fn-1Fn+1 - Fn = (-1)n

The attempt at a solution
Let P(n) = Fn-1Fn+1 - Fn2 = (-1)n where n>= 1

Show it holds for first natural number:
P(1) = F0 + F2 - F12 = -(1) = -1. So it is true

Now assume it works for some k and prove it works for k+1
This is where I'm really not sure what to do. I have tried putting
F(k+1)-1F(k+1)+1 - F(k+1)2 but it ultimately gets me no where.

Usually when I have done inductive proofs I start with some sequence of numbers 1,2,3,4.....,n and show n+1 is there but this one seems slightly different and I'm not sure how to proceed.

Any help is appreciated.
 

Answers and Replies

  • #2
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
15,044
1,625

Homework Statement


The fibonacci numbers are defined by F0 = 0 F1 = 1 and Fn = Fn-1 + Fn-2 for n >= 2.
Use induction the prove the following:
Fn-1Fn+1 - Fn = (-1)n

The attempt at a solution
Let P(n) = Fn-1Fn+1 - Fn2 = (-1)n where n>= 1

Show it holds for first natural number:
P(1) = F0 + F2 - F12 = -(1) = -1. So it is true

Now assume it works for some k and prove it works for k+1
This is where I'm really not sure what to do. I have tried putting
F(k+1)-1F(k+1)+1 - F(k+1)2 but it ultimately gets me nowhere.
You want terms involving ##F_k##, ##F_{k+1}##, and ##F_{k-1}##, so use the defining relation to rewrite ##F_{k+2}##.
 
  • #3
You want terms involving FkF_k, Fk+1F_{k+1}, and Fk−1F_{k-1}, so use the defining relation to rewrite Fk+2F_{k+2}.

Thank you for your reply.

With that I get:
FkFk+2 - F2k+1

Fk(Fk+1 + Fk) - F2k+1

FkFk+1 + F2k - F2k+1

Fk+1(Fk - Fk+1) + F2k

I'm not really sure where to go from this point.
Just to verify that I am thinking of this the right way.
I am trying to find a spot that I can use the assumption made about k where (Fk-1Fk+1 - F2k) and link that to k+1 correct?
 
Last edited:
  • #4
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
15,044
1,625
Thank you for your reply.

With that I get:
FkFk+2 - F2k+1

Fk(Fk+1 + Fk) - F2k+1

FkFk+1 + F2k - F2k+1

I'm not really sure where to go from this point.
Just to verify that I am thinking of this the right way.
I am trying to find a spot that I can use the assumption made about k where (Fk-1Fk+1 - F2k) and link that to k+1 correct?
Yes, that's what you're trying to do. You need to play around with it a bit. The ##F_{k+1}^2## term isn't one you want around, right? What can you do with it?
 
  • #5
Okay so this is what I got:
Fk+1(Fk - Fk-1) + F2k

Fk+1(Fk - Fk - Fk - 1) + F2k

-Fk+1Fk-1 + F2k

Multiply by -1 and get:

Fk+1Fk-1 - F2k = -(-1)k+1

So P(k) = -(-1)k+1

The part about the -1 on the right hand side threw me off at the end but I think it makes sense.

It seems unusual that this is proving k+1 though because it ends with P(k)

And again thank you for your help I have been looking at this problem for longer than I would care to admit.
 
  • #6
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
15,044
1,625
Okay so this is what I got:
Fk+1(Fk - Fk-1) + F2k

Fk+1(Fk - Fk - Fk - 1) + F2k
I'm not sure what you did here. It looks like you introduced a term out of thin air.
 
  • #7
I'm not sure what you did here. It looks like you introduced a term out of thin air.

I made a mistake when I was typing. It should have said Fk+1(Fk - Fk+1) + F2k

Then I used the defining relation on Fk+1 to get the next line.
 

Related Threads on Proof by Induction

  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
4
Views
872
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
1
Views
927
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
4
Views
847
  • Last Post
Replies
2
Views
747
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
12
Views
2K
Top