Proof by Induction: Prove Fn-1Fn+1 - Fn = (-1)^n

[dirtybiscuit]

Homework Statement

The fibonacci numbers are defined by F₀ = 0 F₁ = 1 and F_n = _n-1 + F_n-2 for n >= 2.
Use induction the prove the following:
F_n-1F_n+1 - F_n = (-1)ⁿ

The attempt at a solution
Let P(n) = F_n-1F_n+1 - F_n² = (-1)ⁿ where n>= 1

Show it holds for first natural number:
P(1) = F₀ + F₂ - F₁² = -(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)² 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.

 

[vela]

Homework Statement

The fibonacci numbers are defined by F₀ = 0 F₁ = 1 and F_n = F_n-1 + F_n-2 for n >= 2.
Use induction the prove the following:
F_n-1F_n+1 - F_n = (-1)ⁿ

The attempt at a solution
Let P(n) = F_n-1F_n+1 - F_n² = (-1)ⁿ where n>= 1

Show it holds for first natural number:
P(1) = F₀ + F₂ - F₁² = -(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)² 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}$.

 

[dirtybiscuit]

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:
F_kF_k+2 - F²_k+1

F_k(F_k+1 + F_k) - F²_k+1

F_kF_k+1 + F²_k - F²_k+1

F_k+1(F_k - F_k+1) + F²_k

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 (F_k-1F_k+1 - F²_k) and link that to k+1 correct?

 

[vela]

Thank you for your reply.

With that I get:
F_kF_k+2 - F²_k+1

F_k(F_k+1 + F_k) - F²_k+1

F_kF_k+1 + F²_k - F²_k+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 (F_k-1F_k+1 - F²_k) 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?

 

[dirtybiscuit]

Okay so this is what I got:
F_k+1(F_k - F_k-1) + F²_k

F_k+1(F_k - F_k - F_{k - 1}) + F²_k

-F_k+1F_k-1 + F²_k

Multiply by -1 and get:

F_k+1F_k-1 - F²_k = -(-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.

 

[vela]

Okay so this is what I got:
F_k+1(F_k - F_k-1) + F²_k

F_k+1(F_k - F_k - F_{k - 1}) + F²_k

I'm not sure what you did here. It looks like you introduced a term out of thin air.

 

[dirtybiscuit]

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 F_k+1(F_k - F_k+1) + F²_k

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