 Strong induction

Strong induction establishes a proposition $P(n)$ for all integers $n\ge n_0$. Prove $P(n_0)$; then, for each $n\ge n_0$, assume every $P(k)$ with $n_0\le k\le 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.^[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.