 Strong induction for factorization existence

Every integer $n\ge 2$ 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\le 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.^[ref]

For the chosen number $84$, one possible recursive decomposition isThe 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.

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.