Proof by Induction: Proving fm+n=(fm * fn+1) + (fm-1 * fn) for m,n>=1

[mathrocks]

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.

 

[Muzza]

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.

 

[mathrocks]

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.

 

[whozum]

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.

 

[egsmith]

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).

 

[mathrocks]

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.

 

[whozum]

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.