Originally Posted by

**Laurali224** Hello.

I am stuck on a homework problem.

"Let U(subscript)n be the nth Fibonacci number. Prove by induction on n (without referring to the Binet formula) that U(subscript)m+n=U(subscript)m-1*U(subscript)n + U(subscript)m *U (subscript)n+1 for all positive integers m and n.

So.. I figured out my Base case for n=1.

Um+1=Um-1*U1+Um*U2, which equals Um+1=Um-1+Um, so it is true.

For the Induction Step, I dont know where to go..

Should I prove it P(K-1)--> P(K) or P(K)--> P(K+1).

I've been trying both ways and I am stuck on everything.