Strong Induction Requires No Base Case?

Question

In the book How to Prove It, they say that strong induction requires no base case. My professor's notes also say this. However, while I understand weak and strong induction, as well as the difference and reasoning as to why we would use one versus the other, something about "not having a base case" really bothers me.

The argument made by all those texts which say strong induction requires no base case go as follows. Strong induction requires: if we have that $[\forall k \in N, k<n, P(k)] \rightarrow P(n)$ holds true, then $P(n)$ is true for all $n\in N$.

The argument for $P(0)$ holds true vacuously since $[\forall k \in N, k<0, P(k)]$ is always false (i.e. there are no natural numbers that are less than zero) so we have that $[\forall k \in N, k<0, P(k)] \rightarrow P(0)$. Therefore, $P(0)$ is proven as the base case while proving the inductive hypothesis.

However this is obviously not true. The statement $a \rightarrow b$ doesn't prove $b$ unless $a$ is true. If $a$ is always false, we don't know anything about $b$; we just know that the statement if $a$ then $b$ is correct. So my issue is that we know nothing about $P(0)$. Here I can use "strong induction" to prove something that is false if I don't have to prove a base case:

All natural numbers are even. No base case required. Well, suppose that $[\forall k \in N, k<n, P(k)]$ this is true. Then it's clearly true for $n$, since $n=(n-2)+2$. Since $n-2$ is even by the hypothesis, and $n-2+2$ is just adding 2 to an even number, we still have an even number.

If you required base cases, this would obviously fail. Am I missing something? Why do these books still say that no base case is required? The Wikipedia page for induction still says a base case is needed, and many similar questions on StackExchange regarding this subject seem to be in the middle of a debate around this.

Answer 1

The argument is off a bit: in fact, $[\forall k \in \mathbb{N}, k < 0 \rightarrow P(k)]$ is vacuously true. This is because for any $k \in \mathbb{N}$, $k < 0$ is false, so the implication $k < 0 \rightarrow P(k)$ is true. So, if you've proven the required statement $\forall n \in \mathbb{N}, [ \forall k \in \mathbb{N}, k < n \rightarrow P(k) ] \rightarrow P(n)$, then the special case with $n=0$ always has the hypothesis true, which implies that the conclusion $P(0)$ is also true.

As for your bogus proof that all natural numbers are even: in applying the inductive hypothesis, you're implicitly assuming that $n-2 \in \mathbb{N}$. But for $n=0$ and for $n=1$, this is not valid, so it is not valid to apply the inductive hypothesis. And in fact, $[\forall k \in \mathbb{N}, k < 1 \rightarrow P(k)] \rightarrow P(1)$ is false: the hypothesis is true because the only possible $k$ is $k=0$, but the conclusion $P(1)$ is invalid.

(For a similar situation in which an inductive proof looks good at first, but on closer examination the proof of the inductive step implicitly assumes $n$ is large and the argument breaks down for small $n$: see the bogus proof that "all horses are the same color".)

This illustrates what will often happen in practical proofs by strong induction: there will in fact be cases in which you cannot apply the inductive hypothesis to smaller cases, so you will have to prove those cases by a separate argument. These special cases will end up looking very much like base cases.

So, for instance, the following argument that every natural number is either even or odd is valid: we assume the strong inductive hypothesis $[\forall k \in \mathbb{N}, k < n \rightarrow even(k) \vee odd(k)]$; and we need to prove $even(n) \vee odd(n)$. Now if $n=0$, $n$ is even; and if $n=1$, $n$ is odd. Otherwise, $n-2 \in \mathbb{N}$ and $n-2 < n$, so by the inductive hypothesis, either $n-2$ is even or $n-2$ is odd. In the first case, $n = (n-2) + 2$ is even; in the second case, $n = (n-2) + 2$ is odd.

Answer 2

Strong Induction :

We let $n$ refer to some arbitrary natural number, and by assuming $P(0),..., P(n-1)$, we make a valid argument that this infers, $P(n)$.   Thus we conclude $\forall n\in\Bbb N:P(n)$.

Thus we don't need to prove the base case $P(0)$ is true to make the strong inductive argument.   Although a proof might do so; there is nothing prohibiting it.

The argument for $P(0)$ holds true vacuously since $[\forall k \in N, k<0, P(k)]$ is always false (i.e. there are no natural numbers that are less than zero) so we have that $[\forall k \in N, k<0, P(k)] \rightarrow P(0)$. Therefore, $P(0)$ is proven as the base case while proving the inductive hypothesis.

No, the argument is that $[\forall k\in N, k<0: P(k)]$ is vacuously true.   There does not exist a natural number less than $0$ where the premise does not hold.

So, since $[\forall k\in\Bbb N, k<0:P(k)]$ is vacuously true, and if $[\forall k\in\Bbb N, k<n:P(k)]\to P(n)$ can be proven for an arbitrary natural number, then $P(0)$ will be true.   And then so will $P(1)$, $P(2)$, and cetera.

Still, it is safest to check.

---

All natural numbers are even. No base case required. Well, suppose that $[\forall k \in N, k<n, P(k)]$ this is true. Then it's clearly true for $n$, since $n=(n-2)+2$. Since $n-2$ is even by the hypothesis, and $n-2+2$ is just adding 2 to an even number, we still have an even number.

No, to have a valid strong induction you need an argument that establishes that the truth of $P(n)$ is entailed by $P(k)$ holding for all $k$ which are naturals less than $n$; not just for some of them.