# Fibonacci Numbers Proof

• Oct 12th 2011, 03:22 PM
jstarks44444
Fibonacci Numbers Proof
Hey all, not sure how to proceed with the following proposition:

For all k , m, in the Natural Numbers, where m >= 2,

fib(m+k) = fib(m-1)*fib(k) + fib(m)*fib(k+1)

Tried to fix m and do induction on k, leading to the base case:

fib(m+1) = fib(m-1) + fib(m) which is correct by the definition of fibonacci numbers.

Assume P(n) is true: fib(m+n) = fib(m-1)*fib(n) + fib(m)*fib(n+1)
Now for the inductive step:

fib(m+n+1) = fib(m-1)*fib(n+1) + fib(m)*fib(n+2)

Tried plugging in from P(n) but that doesn't seem to be leading anywhere. I feel like we may need to use strong induction here but I'm not sure how. Any help would be appreciated!
• Oct 13th 2011, 07:49 PM
roninpro
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 $k,m$ (where $m\geq 2$), that

$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 $1,2,\ldots, k$. The reason for this is that the Fibonnaci numbers are defined by the previous two terms in the sequence:

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

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

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

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

Now you have the induction assumption up to $k$ so you could write $F_{m+k}$ and $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.
• Oct 13th 2011, 10:32 PM
Deveno
Re: Fibonacci Numbers Proof
it does work.