# Induction Proof- Fibonacci Numbers

• Feb 16th 2010, 06:04 PM
Laurali224
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.
• Feb 18th 2010, 06:28 AM
Renji Rodrigo
\$\displaystyle F(n+p)=F(p)F(n+1)+F(p-1)F(n).\$

by induction on p, for p=1

\$\displaystyle F(n+1)=F(1)F(n+1)+F(0)F(n)=F(n+1)\$ ok

suposing for s<p+1, in special we have
\$\displaystyle F(n+p)=F(p)F(n+1)+F(p-1)F(n) \$

\$\displaystyle F(n+p-1)=F(p-1)F(n+1)+F(p-2)F(n) \$

lets prove for p+1
\$\displaystyle F(n+p+1)=F(p+1)F(n+1)+F(p)F(n) .\$

we have
\$\displaystyle F(n+p+1)=F(n+p)+F(n+p-1)= \$ by the fibonacci recurrence so

\$\displaystyle = F(p-1)F(n+1)+F(p-2)F(n) +F(p)F(n+1)+F(p-1)F(n)=\$

\$\displaystyle =F(n+1)[F(p)+F(p-1)]+F(n)[F(p-2)+F(p-1)]=F(p+1)F(n+1)+F(p)F(n) .\$