Why are there multiple base cases in this strong induction?

Question

My understanding of needing a base case, in general, is that after proving the induction step, we can assert that the proposition is true for all values from the base case.

This question ($∀n ∈ Z, n≥12$) $\implies$ ( $∃x, y ∈N$ such that $n= 4x + 5y$) uses 3 bases cases for its strong induction solution:

Base cases: $n = 12, 13, 14, 15$

Clearly, $12= 4(3) + 5(0)$, so $P(12)$ is true.

Also, $13= 4(2) + 5(1)$, so $P(13)$ is true.

And, $14= 4(1) + 5(2)$, so $P(14)$ is true.

And, $15= 4(0) + 5(3)$, so $P(15)$ is true

Meanwhile I only used base case, $n=12$. Their rationale for providing multiple cases is as follows

If we didn’t prove $P(13), P(14), P(15)$ as base cases, then the inductive step to get $k+1 = 13, 14,15$ will fail, since proving these assume that $P(r)$, for $ r < 12$, to be true, which we didn’t prove. By establishing base cases $n = 12$ to $n = 15$, the inductive step can then work forward from $n ≥ 15$.

---

The first line starting from "If we..will fail" already contradicts with my understanding of the base case that I mentioned above as proving base case of $12$ should suffice to prove inductive steps for $k+1=13,14,15$.

The part where they said "since proving..we didn't prove" doesn't even make sense to me.Why are they talking about $ r < 12$.

And the last sentence says "work forward from n ≥ 15" confuses me, shouldn't we want it to work from $n ≥ 12$.

My main question is essentially why we do need multiple base cases here? The sub-questions are the 3 paragraphs talking about the solution's rationale for providing multiple cases.

Induction Step(included after a comment by fleabloods):

Note: If the sub-questions should be separately posted, do let me know

Answer 1

Note that in the traditional setup for proof for induction, we establish a base case and then prove that $P(k) \implies P(k+1)$. However, it is difficult to come up with a direct proof of this implication for our case. Note in particular that $P(k) \implies P(k+1)$ requires the additional assumption that $k \geq 12$, since the implication fails with $k = 5$ and $k=10$, for instance.

So, instead of proving this implication, we instead use the implication $P(k) \implies P(k+4)$, which does hold in general and is easy to prove.

With this in mind, we can make sense of the statement

If we didn’t prove $P(13), P(14), P(15)$ as base cases, then the inductive step to get $k+1 = 13, 14,15$ will fail, since proving these assume that $P(r)$, for $ r < 12$, to be true, which we didn’t prove.

For example, if we want to use $P(k) \implies P(k+4)$ in order to prove $P(13)$, we would have to first show that $P(9)$ holds. Indeed, if $k=9$, then $P(k) \implies P(k+4)$ tells us that $P(9) \implies P(13)$. This is problematic because we now require $P(r)$ for $r = 9<12$.

I hope that makes everything a bit clearer.

Answer 2

Your understanding of base case is incorrect. The base cases are simply those cases needed to provide a sufficient foundation for the induction step.

Here the induction step to prove that $P(k+1)$ is true relies on knowing that $P(k-3)$ is true: if there are $x,y\in\Bbb N$ such that $4x+5y=k-3$, then clearly $$4(x+1)+5y=k+1\;,$$ where $x+1,y\in\Bbb N$, so $P(k+1)$ is true. If we’ve verified only that $P(12)$ is true, that argument won’t tell us that $P(13)$ is true: in that case $k=12$, so $k-3=9$, and we’d need to know that $P(9)$ is true in order to use that argument. But as your source says, we didn’t verify that $P(9)$ is true, so that argument simply isn’t valid.

As it happens, $P(9)$ is true, so if we’d checked it as a base case, we could have used the induction step to see that $P(13)$ is true. $P(10)$ is also true, so we could have verified it as part of the base case and used the induction step to see that $P(14)$ is true. But $P(11)$ is not true, so there is no possible way to use the induction step to derive $P(15)$. It turns out that $11$ is the last failure: $12$ is the smallest integer such that $P(n)$ is true for it and every larger integer.

The induction works only after we know that $P(n)$ is true for four consecutive integers $n$: if $P(n)$, $P(n+1)$, $P(n+2)$, and $P(n+3)$ are true, the truth of $P(n)$ allows us to use the induction step to prove that $P(n+4)$ is true, the truth of $P(n+1)$ allows us to use the induction step to prove that $P(n+5)$ is true, and so on. But we need those four consecutive integers: if $P(n)$ and $P(n+1)$ were true, but $P(n+2)$ were not, the induction step would give us the truth of $P(n+4)$ and $P(n+5)$, but not the truth of $P(n+6)$, because for that we’d need to know that $P(n+2)$ was true.

Thus, the induction argument in this example really does use all four parts of the base case, $P(12)$, $P(13)$, $P(14)$, and $P(15)$: without them, the argument falls apart at one of the next four cases.

Answer 3

You didn't include what the induction step was!

We can't evaluate their argument if we don't know what the induction step was.

But from their commentary I suspect the induction step is something like:

If it is true for $n$ and for all values between $12$ and $n$ then it should be true for $n-3$ (assuming $n-3$ is between $12$ and $n$); then $n-3 = 4x + 5y$ for some $x,y$. So $n+1 = 4(x+1) + 5$.

But what's wrong with that?

Let's try it on $12$. Let's try to go from $12$ to $13$. It is true for $12$ and for all values between $12$ and $12$. So it should be true for $12-3=9$ (assuming $12-3=9$ is between $12$ and $12$) and ..... ....!!!!skreech!!!!!.....

NO! $9$ is not between $12$ and $12$ so we can't use the induction step.

Okay we'll can figure out a special case for $13$. So we now have that is it true for all $13$ and all numbers between $12$ and $13$.

Let's try to use the induction step to go from $13$ to $14$. It is true for $13$ and for all values between $12$ and $13$. So it ought to be true for $13-3=10$ so long as $10$ is between.... Oh G#@%!

So we do a special case for $14$.

But, lord, how long can this go on?! How many special cases will we have to do before we can do the induction step and never worry about special cases?

Well, we can do our induction step if we can assume that $n-3$ is between $12$ and $n$. But for $n-3$ to be between $12$ and $n$ we must have $n$ at least $15$. So we can't use our induction step untill we have gotten to $15$

So we need special base cases for $12,13,14$ and $15$.

======

Note: We do have $12 -3 =9$ and we can do $9 = 1*4 + 1*5$ so $13 = (1+1)*4 + 1*5 = 2*4 + 5$. But we have to have shown $9$ was possible first.

Likewis we could have gotten $14$ from $10$. But we can't have gotten $15$ from $11$ because $11 = 4x + 5y$ is impossible. Note: $15 = 0*4 + 3*5$ is the only way to do this and there are not $4$s so we can't have gotten $15$ from $11$ but just adding only more $4$.