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