Return to Answer

One may transform any strong induction proof into one which (legalistically speaking!) doesn't explicitly treat the base case.

Proving $P(n)$ by induction, one assumes $ \forall k<n \ P(k)$ which weakens to $\forall k<n\ P(0)\implies P(k)$.` Now one may adapt whatever proof one had for the induction step to establish from this that $P(0)\implies P(n)$. Now one proves $P(0)$ and concludes $P(n)$ by modus ponens.

Yes, I know, morally the base case still got special treatment, but formally now that happens in the induction step. Thus finding a formal distinction between theorems that require special treatment for the base case and those that don't seems impossible.

In any case, if you can prove $P(n)$ by strong induction, you can prove $P(0)\implies P(n)$ by strong induction with no special treatment for the base case, morally or formally. So examples abound.

One may transform any strong induction proof into one which (legalistically speaking!) doesn't explicitly treat the base case.

Proving $P(n)$ by induction, one assumes $ \forall k<n \ P(k)$ which weakens to $\forall k<n\ P(0)\implies P(k)$.` Now one may adapt whatever proof one had for the induction step to establish from this that $P(0)\implies P(n)$. Now one proves $P(0)$ and concludes $P(n)$ by modus ponens.

Yes, I know, morally the base case still got special treatment, but formally now that happens in the induction step. Thus finding a formal distinction between theorems that require special treatment for the base case and those that don't seems impossible.

In any case, if you can prove $\forall n\geq 0\ P(n)$ by strong induction, you can prove $\forall n>0 \ P(0)\implies P(n)$ by strong induction with no special treatment for the base case, morally or formally. So examples abound.

One may transform any strong induction proof into one which (legalistically speaking!) doesn't explicitly treat the base case.

Proving $P(n)$ by induction, one assumes $ \forall k<n \ P(k)$ which weakens to $\forall k<n\ P(0)\implies P(k)$.` Now one may adapt whatever proof one had for the induction step to establish from this that $P(0)\implies P(n)$. Now one proves $P(0)$ and concludes $P(n)$ by modus ponens.

Yes, I know, morally the base case still got special treatment, but formally now that happens in the induction step. Thus finding a formal distinction between theorems that require special treatment for the base case and those that don't seems impossible.

One may transform any strong induction proof into one which (legalistically speaking!) doesn't explicitly treat the base case.

Proving $P(n)$ by induction, one assumes $ \forall k<n \ P(k)$ which weakens to $\forall k<n\ P(0)\implies P(k)$.` Now one may adapt whatever proof one had for the induction step to establish from this that $P(0)\implies P(n)$. Now one proves $P(0)$ and concludes $P(n)$ by modus ponens.

Yes, I know, morally the base case still got special treatment, but formally now that happens in the induction step. Thus finding a formal distinction between theorems that require special treatment for the base case and those that don't seems impossible.

In any case, if you can prove $P(n)$ by strong induction, you can prove $P(0)\implies P(n)$ by strong induction with no special treatment for the base case, morally or formally. So examples abound.

If you can prove $\forall n\geq 0\ P(n)$ by strong induction (possibly treating the base case as special), then you can't prove $\forall n\geq 1\ P(0)\implies P(n)$ by strong induction without treating the base case as special?

This trivial remark only means to show that in principle that one has such proofs at hand whenever one has a strong induction of any sort.

One may transform any strong induction proof into one which (legalistically speaking!) doesn't explicitly treat the base case.

Proving $P(n)$ by induction, one assumes $ \forall k<n \ P(k)$ which weakens to $\forall k<n\ P(0)\implies P(k)$.` Now one may adapt whatever proof one had for the induction step to establish from this that $P(0)\implies P(n)$. Now one proves $P(0)$ and concludes $P(n)$ by modus ponens.

Yes, I know, morally the base case still got special treatment, but formally now that happens in the induction step. Thus finding a formal distinction between theorems that require special treatment for the base case and those that don't seems impossible.