# Math Help - Fibonacci Sequence - Induction Proof

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

2. 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 $n\leq k$ where k is an arbitary integer.

Assume P(k) is true and prove P(k+1) is true.

3. 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 $k$ and induct on $n$, treating $k$ as a constant.

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