4
$\begingroup$

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$
4
$\begingroup$

$P$ holds vacuously for every natural number smaller than $0$. Hence by the induction hypothesis, $P$ holds for $0$.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Bram28 Jul 13 '17 at 16:37
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$
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.