|1||[made Community Wiki]|
Strong induction without a base case
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.