Why is complete strong induction a valid proof method and not need to explicitly proof the base cases?

Solution 1:

A valid proof by complete induction includes a uniform proof for all $k$ of the inferences below. As such it necessarily includes a proof ($\rm\color{#0a0}{vacuous}$) of the base case $\color{#c00}{\,P(0)}.\,$ See the schema below.

$$\begin{align} \color{#0a0}{\bbox[3px,border:2px solid #0a0]{\phantom{:}}}\Rightarrow\,\color{#c00}{ P(0)}\\ P(0)\Rightarrow\, P(1)\\ P(0),P(1)\Rightarrow\, P(2)\\ \vdots\qquad\ \ \ \ \\ P(0),P(1),\ldots,P(k-1)\,\Rightarrow\,P(k)\\ \end{align}\qquad\qquad\qquad\qquad\ \ $$

While a valid inductive proof necessarily implies a proof of $\,\color{#c00}{P(0)},\,$ this may not occur explicitly. Rather, it may be a special case of a much more general implication derived in the proof. For example, in many such proofs the natural base case(s) is not a single number but rather a much larger set. Let's examine a simple induction where the base cases are all odd naturals.

If $n\ge\color{#c00}1$ is an integer then $\,n = 2^{\large i} j\, $ for some odd $j$ and some integer $i\ge 0.\,$ For if $n$ is odd then $n = 2^0 n,\,$ else $\,n = 2k\,$ for $\,1 \le k < n\,$ so induction $\,\Rightarrow k = 2^{\large i} j,\,$ so $\, n = 2k = 2^{\large i+1} j.\ \ $ QED

Here the base case $\color{#c00}{P(1)}$ is not explicitly proved. Instead it is a special case of the more general inference that $\,n\,$ odd $\,\Rightarrow\, n = 2^0 n.\,$ In such factorization (decomposition) problems the natural base cases are all irreducibles (and units) - not only the $\rm\color{#c00}{least}$ natural in the statement, e.g. in the proof of existence of prime factorizations of integers $\,n > 1,\,$ with base cases being all primes.

Remark $ $ The same holds for infinite descent - the contrapositive form of complete induction: $\, $ if given a counterexample $\,\lnot P(n)\,$ we can prove there exists a smaller one $\lnot P(k),\ k < n,\,$ then no counterexample exists, else iterating the proof would yield an infinite descending chain of counterexamples, contra $\,\Bbb N\,$ is well-ordered. Or, reformulated, if there is a counterexample then, by well order, we can choose a minimal counterexample (a.k.a. minimal criminal), contra the proof yields a smaller one.

Solution 2:

if we show $ P(m), m<n \implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b \in BaseCases$)

Right, that's exactly correct: if there is nothing smaller than $0$ (as is the case for the natural numbers) then it is vacuously true that:

$$P(m) \text{ holds for any } m<0 \tag{1}$$

So, if you have shown that:

$$\text{for any } n: \text{ if } P(m) \text{ holds for any } m<n, \text{ then } P(n) \tag{2}$$

then in particular you have shown that:

$$\text{ if } P(m) \text{ holds for any } m<0, \text{ then } P(0) \tag{2'}$$

and so we get

$$P(0)$$

by Modus Ponens on $(1)$ and $(2')$

So, there is indeed no need to prove an explicit base case.

That said, think about how in practice you would actually prove $(2)$. Probably, you would be able to show $P(n)$ based on the assumption that there actually are $m<n$ for which we can show that if they all have property $P(m)$, then $P(n)$. But for the edge case of $n=0$, there are no such $m<n$ ... so ... you need to show $P(0)$ by itself!

In other words, in practice, you often do have to treat the base cases as special cases that you prove as base cases after all.