Induction Proof- Fibonacci Numbers
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.