Re: Fibonacci Numbers Proof

First I'd like to TeX this so that others can read what you wrote. (Please consider writing your problem in LaTeX next time.) You are trying to show that for all integers $\displaystyle k,m$ (where $\displaystyle m\geq 2$), that

$\displaystyle F_{m+k}=F_{m-1}F_k+F_m F_{k+1}$

I think that using induction is a fine idea. The only slight change I would make is to use strong induction, where we assume that the formula works for $\displaystyle 1,2,\ldots, k$. The reason for this is that the Fibonnaci numbers are defined by the previous two terms in the sequence:

$\displaystyle F_{k+1}=F_{k}+F_{k-1}$

Weak induction would technically only allow us to say something about the $\displaystyle F_k$ term, but not the other $\displaystyle F_{k-1}$ term.

Technical details aside, to complete the induction, you tried to show that the formula works for $\displaystyle F_{m+k+1}$, but got stuck. I recommend using that recursion relation above:

$\displaystyle F_{m+k+1}=F_{m+k}+F_{m+k-1}$

Now you have the induction assumption up to $\displaystyle k$ so you could write $\displaystyle F_{m+k}$ and $\displaystyle F_{m+k-1}$ using the formula. Try it out and see where it goes. (I haven't actually carried it out myself, but I would expect it to work.) Let us know how it turns out.

Re: Fibonacci Numbers Proof