Strong induction and well-ordering

In strong induction, the step at an integer n assumes the property for all domain elements smaller than n and proves it at n. This is useful when you cannot predict in advance which smaller size a decomposition will produce. You still need to deal with the smallest sizes, for which the hypothesis may be empty. If the argument uses two previous terms, two initial cases are normally needed to ensure that each referenced term belongs to the established range.

Strong induction and ordinary induction prove the same kinds of claims over natural numbers. To convert strong induction into ordinary induction, let Q(n) assert that every case from the starting value through n is true. Knowing Q(n) provides the collection of earlier cases needed for the strong step, so Q(n + 1) follows. The word “strong” describes the amount of information available inside a step, not extra power to establish false statements or bypass missing boundary cases.

The well-ordering principle says every nonempty subset of the nonnegative integers has a least element. The restriction to a well-ordered domain matters. The integers themselves have no least element, and the positive real numbers have no smallest member because half of any member is a smaller positive member. Before invoking well-ordering, identify the set explicitly, show it is nonempty under your temporary assumption, and show its elements lie in a domain where the principle applies.

To prove a universal statement by a least counterexample, assume the set of failing natural numbers is nonempty and choose its least member n. Every earlier admissible case then satisfies the statement; otherwise n would not be least. Use those established cases to contradict failure at n. This is the same information as a strong induction hypothesis, repackaged inside a contradiction proof. The method does not authorize a vague choice of “the simplest” object until simplicity is measured by a well-founded quantity.

Prime factorization existence is a natural application. For an integer n at least two, either n is prime or it is a product of two integers strictly between one and n. The strong hypothesis gives prime-product representations for both smaller factors. Concatenating those lists gives one for n. This proves existence of a prime decomposition, but not its uniqueness; uniqueness requires additional divisibility arguments that should not be smuggled into the conclusion.

The strict inequalities are the heart of the reasoning. Splitting n as one times n provides no smaller instance, and a recursive proof using the same unresolved size merely restates the problem. In algorithms, attach an integer measure to every recursive call and verify it decreases while staying bounded below. Strong induction then matches the dependency graph. A decrease in one component is insufficient if another unbounded component can reset the measure without a carefully defined ordering.