= Strong induction and accumulated hypotheses
<Strong induction> does not prove more than ordinary <mathematical induction>. Put $Q(n)=\bigwedge_{k=n_0}^{n}P(k)$. Ordinary <mathematical induction> on $Q$ retains the earlier cases and obtains the next one, establishing the same conclusion. Conversely, an ordinary <inductive step> can ignore the extra cases allowed in a <strong induction> hypothesis.<Mathematics for Computer Science by Eric Lehman and others>[§5.3, printed pp. 129–130: equivalence of induction formats and well ordering]{ref}
The <well-ordering principle> gives another view. A least <counterexample> would have all smaller cases true, so the <strong induction> step would establish that allegedly false case. The starting case excludes the beginning.
Back to article page
