Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
$P$ holds vacuously for every natural number smaller than $0$. Hence by the induction hypothesis, $P$ holds for $0$.
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.
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.
