Induction proofs: fibonacci numbers

[LOLChris]

Homework Statement

Use induction to prove this equation:

F(n+k) = F(k)F(n+1) + F(k-1)F(n)

Homework Equations

F(0)=0 and F(1)=1
F(n)=F(n-1)+F(n-2)

The Attempt at a Solution

Base: n=0, k=1
F(1)=(1*1)+(0*0)=1

True for n=k

k=k+1
F(2k+1) = F(k)F(k+2) + F(k-1)F(k+1)

Here is where I get stuck, I'm not sure how to manipulate this equation to show they are equal. I'm pretty sure I can solve it using only the relevant equations above.

 

[MathematicalPhysicist]

Well if you pick your induction on for example on n, you get:

F(n+k+1)=F(n+k)+F(n+k-1)
You need to use here a different induction which asserts that if we assume that it's true for all s<n then it's true for s=n.

So this means that:
F(n+k)=F(k)F(n+1)+F(k-1)F(n)
F(n+k-1)=F(k)F(n)+F(k-1)F(n-1)
add them and you get the required equality, use F(n+1)+F(n)=F(n+2) and F(n)+F(n-1)=F(n+1).

 

[Office_Shredder]

True for n=k

k=k+1
F(2k+1) = F(k)F(k+2) + F(k-1)F(k+1)

Here is where I get stuck, I'm not sure how to manipulate this equation to show they are equal. I'm pretty sure I can solve it using only the relevant equations above.

Be careful! The k that you're using in your inductive hypothesis and the k in the original problem are not the same number

 

[LOLChris]

Well if you pick your induction on for example on n, you get:

F(n+k+1)=F(n+k)+F(n+k-1)
You need to use here a different induction which asserts that if we assume that it's true for all s<n then it's true for s=n.

So this means that:
F(n+k)=F(k)F(n+1)+F(k-1)F(n)
F(n+k-1)=F(k)F(n)+F(k-1)F(n-1)
add them and you get the required equality, use F(n+1)+F(n)=F(n+2) and F(n)+F(n-1)=F(n+1).

Thanks, once I realized I could substitute for F(n+k) it was all downhill from there.

One question, when writing an induction proof for equations like this with two variables (n and k), should you prove 'n+1' or 'k+1'? Or both?