# Proof by induction

The following question has been giving me problems because I'm stuck trying to find what the base cases would be.

Let m be a given positive integer with m>=2(So m remains constant throughout the problem) Let fn be the sequence of fibonacci numbers. Prove that for every integer n>=1, fm+n=(fm * fn+1) + (fm-1 * fn).

I'm not sure how I go about finding the base cases to start the proof. I know I'm suppose to set something equal to >=1 but I'm not sure what.

## Answers and Replies

If you want to do induction on n, the base case involve setting n = 1 and proving that f(m + 1) = f(m) * f(2) + f(m - 1) * f(1) (for m >= 2). That statement is obviously true (see the definition of the Fibonacci sequence).

I think this problem requires strong induction too, btw.

Last edited:
Muzza said:
If you want to do induction on n, the base case involve setting n = 1 and proving that f(m + 1) = f(m) * f(2) + f(m - 1) * f(1) (for m >= 2). That statement is obviously true (see the definition of the Fibonacci sequence).

I think this problem requires strong induction too, btw.

But my teacher has told us that in this specific problem there are more than one base case needed.

For induction you need two bases. Do it for n=1 and n=2 , and from there you should be able to state that induction proves the idea.

I think this problem requires a sort of nested induction and that's what your teacher was hinting at.
First you have to prove the fn statement for m=2 (using induction),
then you have to prove the m+1 case of the fn statement (using induction again).

whozum said:
For induction you need two bases. Do it for n=1 and n=2 , and from there you should be able to state that induction proves the idea.

But where did you come up with the base cases needing to be n=1 and n=2. My teacher tried to explain a mathematical way of figuring out the base cases to use but I couldn't follow it.

The basic principle of induction is:
If a function is true for a base 'n' and true for the base 'n+1' , then it will be true for all n.

So if you can prove that your idea is true for a number 'n', and a number 'n+1' then you have proven that it will be true for any number larger than n. Conventionally you start at n=0 or n=1, it follows from the laws of continuity that induction holds.