# Induction proofs: fibonacci numbers

## 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.

Related Calculus and Beyond Homework Help News on Phys.org
MathematicalPhysicist
Gold Member
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
Staff Emeritus
Gold Member
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

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?