Strong induction and vacuous truth I was pondering a bit more about this question regarding being able to "omit" the base case in a proof by strong induction due to vacuous truth. The post states: > Strong induction proves a sequence of statements $P(0), P(1), …$ 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. However, if we consider $n=0$, we would have that the statement is vacuously true, which I would take to mean that the implication is true _regardless_ of the validity of $P(0)$. However, clearly it's necessary for $P(0)$ to hold for an induction proof to be valid. So I'm confused on how, by omitting the base case, $n=0$ isn't just a tautology, making the implication true regardless of whether $P(0)$ actually holds.

Strong (or : complete) induction_induction) is :

> $(∀n)[(∀m)(m < n \to P(m)) \to P(n)] \to (∀n) P(n)$.

So, in order to conclude with $(∀n) P(n)$ we have to show that : $(∀n)[(∀m)(m < n \to P(m)) \to P(n)]$ holds.

If I understand well, your concern is with $n=0$.

In that case, we have :

> $(∀m)(m < 0 \to P(m)) \to P(0)$.

But $(m < 0 \to P(m))$ is _vacuously true_ (there are no $m < 0$). Thus, the conditional amounts to : $\text T \to P(0)$ and there is only one possibility to satisfies it : when $P(0)$ is true.