# Proof by Induction

Tags:
1. Feb 13, 2015

### dirtybiscuit

1. The problem statement, all variables and given/known data
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.

2. Feb 13, 2015

### vela

Staff Emeritus
You want terms involving $F_k$, $F_{k+1}$, and $F_{k-1}$, so use the defining relation to rewrite $F_{k+2}$.

3. Feb 14, 2015

### dirtybiscuit

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: Feb 14, 2015
4. Feb 14, 2015

### vela

Staff Emeritus
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. Feb 14, 2015

### dirtybiscuit

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. Feb 14, 2015

### vela

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

7. Feb 15, 2015

### dirtybiscuit

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.