# Fibonacci Sequence - Induction Proof

• Jan 19th 2011, 03:23 PM
WWU
Fibonacci Sequence - Induction Proof
Hello,

I am having problems with writing an inductive proof for the following problem:

=> Prove by induction that F(n+k) = F(k)F(n+1) + F(k-1)F(n)

Now I know that my basis is: F(0) = 0 and F(1) = 1

I am having trouble even getting started or figuring out where to start, any tips would be much appreciated!
• Jan 19th 2011, 03:32 PM
dwsmith
Quote:

Originally Posted by WWU
Hello,

I am having problems with writing an inductive proof for the following problem:

=> Prove by induction that F(n+k) = F(k)F(n+1) + F(k-1)F(n)

Now I know that my basis is: F(0) = 0 and F(1) = 1

I am having trouble even getting started or figuring out where to start, any tips would be much appreciated!

With induction, you let $\displaystyle n\leq k$ where k is an arbitary integer.

Assume P(k) is true and prove P(k+1) is true.
• Jan 19th 2011, 03:41 PM
chiph588@
Quote:

Originally Posted by WWU
Hello,

I am having problems with writing an inductive proof for the following problem:

=> Prove by induction that F(n+k) = F(k)F(n+1) + F(k-1)F(n)

Now I know that my basis is: F(0) = 0 and F(1) = 1

I am having trouble even getting started or figuring out where to start, any tips would be much appreciated!

You should fix $\displaystyle k$ and induct on $\displaystyle n$, treating $\displaystyle k$ as a constant.

Your base case is $\displaystyle F(k) = F(k)F(1)+F(k-1)F(0)$.