Thread: Induction Proof- Fibonacci Numbers

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 stuck on everything.

by induction on p, for p=1

ok

suposing for s<p+1, in special we have




lets prove for p+1


we have
by the fibonacci recurrence so