Induction proofs: fibonacci numbers

  • Thread starter LOLChris
  • Start date
  • #1
2
0

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.
 

Answers and Replies

  • #2
MathematicalPhysicist
Gold Member
4,294
203
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).
 
  • #3
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99
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
 
  • #4
2
0
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?
 

Related Threads on Induction proofs: fibonacci numbers

  • Last Post
Replies
1
Views
15K
  • Last Post
Replies
13
Views
3K
  • Last Post
Replies
11
Views
4K
Replies
7
Views
9K
  • Last Post
Replies
5
Views
3K
Replies
11
Views
19K
Replies
7
Views
4K
Replies
3
Views
7K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
7
Views
2K
Top