# Strong induction doesn't require a base case?

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$.
• This is wrong! You need to show that $P$ holds for $0$ given the inductive hypothesis that it holds for all natural numbers smaller than $0$. So for the $0$ case the inductive hypothesis holds vacuously, but it does not follow from this that $P$ holds for $0$. You still need to demonstrate that! Jul 13, 2017 at 16:37
• But if we prove the inductive step i.e., $\forall n\in \mathbb N( \forall k\in \mathbb N(k<n\implies P(k))\implies P(n))$, we have effectively also proven the base case since for $n=0$, the statement is $$\forall k\in \mathbb N(k<0\implies P(k))\implies P(0)$$ which is the same as $\top\implies P(0)$ which indicates that $P(0)$ must hold. Feb 11, 2021 at 15:21
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.