1. ## 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!

2. ## 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.

3. ## Re: Fibonacci Numbers Proof

it does work.