Strong induction and accumulated hypotheses
ID: strong-induction-and-accumulated-hypotheses
Strong induction does not prove more than ordinary mathematical induction. Put . Ordinary mathematical induction on 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.[ref]
Mathematics for Computer Science by Eric Lehman and others. §5.3, printed pp. 129–130: equivalence of induction formats and well ordering
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.
New to topics? Read the docs here!