I'm considering the natural numbers to be the nonnegative integers. The principle of strong induction can be stated as follows,
"If $P$ is a property such that for any $x$, if $P$ holds for all natural numbers less then $x$, then $P$ holds for $x$ as well, then $P$ holds for all natural numbers $x$."
This doesn't require a base case. My question is why? Shouldn't $P$ hold for $0$ for the induction to work?
$\endgroup$ 13 Answers
$\begingroup$$P$ holds vacuously for every natural number smaller than $0$. Hence by the induction hypothesis, $P$ holds for $0$.
$\endgroup$ 2 $\begingroup$If you know that $P$ holds for $x$ whenever $P$ holds for all $y$ with $y < x$, then the special case for $x = 0$ tells you that $P$ holds for $0$. This is because there are no $y < 0$, and so $P$ holds for all $y$ with $y < 0$ is vacuously true.
$\endgroup$ $\begingroup$Indeed strong induction does not require an explicit base case. However, for the case of $0$ the induction hypothesis is vacuously true, which provides no information. Therefore, the proof for $0$ must effectively by done from scratch.
It might be that the same proof that works for the general case also works for the case $0$, and for that case indeed produces a proof from scratch. Cases where there is really a uniform proof that does not require any special consideration for $0$ are quite rare however.
$\endgroup$
