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!