discrete mathematics - Strong Mathematical Induction: Why More than One Base Case?

I am trying to understand this example of strong induction. I know normal induction. In normal induction, if base case is true then we assume some number $n$ to be true. Afterwards, we prove $n+1$ is true.

In strong induction, as you can see below, you prove more than 1 base case. I am not sure why. Then you prove $n+1$ is true...

I don't know why or how they choose however many base cases to prove or why proving extra base cases matters. Could someone please explain the inductive step of $3 + n - 2$? Where did it come from?

Answer

Arturo's answer is very correct, but since you said you haven't understand much, I will just try to rephrase some points.

First, it's important to notice that as it is, the proof (or the statement is wrong). The correct statement is, as stated by Arturo:

An n-cent postage where n is greater or equal than 12 can be made up using 3-cents and 7 -cents stamps.

It's actually quite simple to see that it is not true for any n, for instance, you can't make up a 2-cents postage with only 3-cents and 7-cents stamps. So the base case (where the induction can start) will be n=12, and not n=0 or n=1. You can prove the base case by showing that 12 = 3 + 3 + 3 + 3.

Now, you could try to use simple induction, and to say let's assume P(n) is true, and let's show that P(n+1) is also true. The problem is that you won't be able to show that, because knowing how to make a n-cent postage with 3-cents and 7-cents stamps does not help you to make a n+1-cent postage! For instance, a 20-cents postage can be made as 7+3+7+3. But a 21-cents postage is made using 7+7+7.

In other words, you can't reuse P(n) in order to prove P(n+1).

However, you can see that if you know how to make a n-cent postage, you also know how to make a n+3-cent postage, because it's enough to take the n-cents postage, and to add a 3-cents stamp. So, if you know P(n), then you can also prove P(n+3).

Intuitively, the problem is that because you need to make a step of 3 instead of 1, then you need to prove the base case for B, B+1 and B+2, where B is your starting value, that is, B=12 in this case. So, you need to show that P holds for 12, 13 and 14, which is the case.

Now, your proof holds, because intuitively:

• it holds for 12, as showed


• it holds for 13, as showed


• it holds for 14, as showed,


• it holds for 15, because it holds for 12, and if it holds for N, it also holds for N+3


• it holds for 16, because it holds for 13, and if it holds for N, it also holds for N+3


• it holds for 17, because it holds for 14, and if it holds for N, it also holds for N+3


• it holds for 18, because it holds for 15, and if it holds for N, it also holds for N+3



• etc

So, I'd say that in this case, you use the strong induction because you can't use the simple induction, as you would be unable to prove the simple induction step. I hope it clarifies things a bit.