= Strong induction for factorization existence
Every <integer> $n\geq2$ has a <prime factorization>. The <induction base case> $2$ is <prime>. For a larger <integer>, either it is <prime> or it is $ab$, with $2\leq a,b<n$. The <induction hypothesis> supplies <prime factorizations> of both smaller <integer divisors>; multiplying them gives one for $n$. This proves existence, while uniqueness requires the additional argument under the <fundamental theorem of arithmetic>.<Mathematics for Computer Science by Eric Lehman and others>[§5.2.2, printed pp. 125–126: existence of a product of primes; the statement here does not include uniqueness]{ref}
For the chosen number $84$, one possible recursive decomposition is
$$
84=6\cdot14=(2\cdot3)(2\cdot7)=2^2\cdot3\cdot7.
$$
The step at $84$ needs results for $6$ and $14$, rather than a result for $83$. Each <composite number> in this <factorization tree> splits into strictly smaller positive <integers>, so recursive descent terminates at <prime numbers>. The <tree> describes one construction; another choice of <integer divisors> can give a differently shaped <factorization tree>.
\Image[/strong-induction-factorization-dependency-tree.png]
{title=The step for 84 can use 6 and 14: the induction hypothesis covers both}
{description=Original factorization tree $84\to6\cdot14$, followed by $6\to2\cdot3$ and $14\to2\cdot7$. Arrows show recursive dependencies toward smaller <integers>, rather than the order of increasing induction. The strip at the bottom marks the earlier cases available at the step for $84$, with the required $6$ and $14$ highlighted. No use of the unproved case $84$ is permitted in the hypothesis.}
The same pattern explains the usefulness of <strong induction> for <algorithm correctness>. When a <recursive procedure> returns answers for smaller <inputs>, the <induction hypothesis> can justify those answers; the remaining task is to justify how the current call combines them. Strictly decreasing a <nonnegative integer> size measure establishes termination. Correctness also requires each call's conditions and its combination rule; termination alone does not make an <algorithm> correct.
Back to article page
