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!

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 where k is an arbitary integer.

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

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

Your base case is .