Strong induction proves a sequence of statements $P(0)$, $P(1)$, $\ldots$ by proving the implication
"If $P(m)$ is true for all nonnegative integers $m$ less than $n$, then $P(n)$ is true."
for every nonnegative integer $n$. There is no need for a separate base case, because the $n=0$ instance of the implication is the base case, vacuously. But most strong induction proofs nevertheless seem to involve a separate argument to handle the base case (i.e., to prove the implication for $n=0$).
Can you think of a natural example of a strong induction proof that does not treat the base case separately? Ideally it should be a statement at the undergraduate level or below, and it should be a statement for which strong induction works better than ordinary induction or any direct proof.
Best Answer
My example is the classical proof that sqrt(2) is irrational.
More generally, many proofs that proceed by showing that there are no minimal counterexamples exemplify your phenomenon. The method of no-minimal-counterexamples is exactly the same as strong induction, but where one proves the required implication by contradiction. In many applications of this method, it is often clear that the smallest numbers are not counterexamples, and this would not ordinarily regarded as a separate base "case".
In the classical proof that sqrt(2) is irrational, for example, we suppose sqrt(2) = p/q, where p is minimal. Now, square both sides and proceed with the usual argument, to arrive at a smaller counterexample. Contradiction! This amounts to a proof by strong induction that no rational number squares to 2, and there seems to be no separate base case here.
People often carry out the classical argument by assuming p/q is in lowest terms, but the argument I just described does not need this extra complication. Also, in any case, the proof that every rational number can be put into lowest terms is itself another instance of the phenomenon. Namely, if p/q is a counterexample with p minimal, then divide by any common factor and apply induction. There seems to be no separate base case here where it is already in lowest terms, since we were considering a minimal counterexample. Perhaps someone objects that there is no induction here at all, since one can just divide by the gcd(p,q). But the usual proof that any two numbers have a gcd is, of course, also inductive: considering the least linear combination xq+yp amounts to strong induction, again with no separate base case.