= Strong induction
{title2=$P(n_0),\quad[\forall k\in\{n_0,\ldots,n\},\ P(k)]\Rightarrow P(n+1)$}
{wiki}
<Strong induction> establishes a <proposition> $P(n)$ for all <integers> $n\geq n_0$. Prove $P(n_0)$; then, for each $n\geq n_0$, assume every $P(k)$ with $n_0\leq k\leq n$ and prove $P(n+1)$. The <induction hypothesis> includes all earlier cases, so the <inductive step> can use whichever smaller indices it needs. It cannot use $P(n+1)$ itself.<Mathematics for Computer Science by Eric Lehman and others>[§5.2.1, printed p. 125: strong induction principle]{ref}
This is useful when a construction breaks into smaller pieces of varying sizes. A <prime factorization> splits a <composite number> into smaller <integer divisors>, which need not be one less than the original <integer>. A <recursive procedure> can likewise call itself on several smaller <inputs>. The available cases should match those dependencies. <Strong induction> lets the <mathematical proof> follow the construction rather than forcing every step through the immediately preceding size.
Back to article page
