6.5 Recursion and Induction

Recursion and induction are paired patterns. Recursion defines objects step by step. Induction proves statements about objects built step by step.

The natural numbers give the basic model. Start with $0$. Then repeatedly apply the successor operation:

Each number is either the starting value or obtained from an earlier number. This recursive construction supports the principle of induction.

To prove a statement $P(n)$ for all natural numbers $n$, it is enough to prove two things:

and

The first part is the base case. The second part is the induction step. Together, they cover every natural number because every natural number is reached by repeated successor steps.

Recursion defines. Induction verifies.

For example, the factorial function is defined recursively by

and

The value at each stage depends on the previous value. This gives a finite procedure for computing $n!$ for any natural number $n$.

One can then prove properties of factorials by induction. For instance, to show that $n! \geq 1$ for all $n$, prove it for $0$, then show that if $n! \geq 1$, then $(n+1)! \geq 1$.

The same pattern appears beyond numbers. Lists are recursive objects. A list is either empty or formed by adding an element to the front of a smaller list. Trees are recursive objects. A tree may consist of a root together with smaller subtrees. Formal expressions are recursive objects built from variables and operations.

Because these objects are recursively formed, induction is the natural proof method for them.

For lists, one proves a property by checking the empty list and then proving that adding one element preserves the property. For trees, one proves the base case for a leaf and then proves the step for a node assuming the property for its subtrees. For formulas, one proves the result for atomic formulas and then checks each way of building larger formulas.

This is called structural induction. The proof follows the construction of the object.

Recursion is also central in algorithms. Many algorithms solve a problem by reducing it to smaller instances. To sort a list, one may sort smaller lists and merge them. To search a tree, one searches subtrees. To compute powers, one may reduce the exponent step by step.

The proof of correctness usually mirrors the recursion. If the algorithm is correct on smaller inputs and the combining step is correct, then the algorithm is correct on the larger input.

For example, a recursive definition of powers is

and

Induction proves the laws that follow from this definition, such as

The proof proceeds by induction on $n$ or $m$, depending on how the recursion is arranged.

Recursion must be controlled. A recursive definition is valid only when each step reduces the problem toward a base case. Without this decrease, the definition may not determine an object.

For natural numbers, the decrease is clear: $n+1$ depends on $n$. For lists, a nonempty list depends on a shorter list. For trees, a tree depends on smaller subtrees.

This condition is called well-foundedness. It prevents infinite descent.

Induction also depends on well-foundedness. A proof works because there are no endlessly descending chains of smaller cases. Every case eventually reaches a base case.

There are several forms of induction.

Ordinary induction proves $P(n)$ from $P(n-1)$. Strong induction proves $P(n)$ assuming $P(k)$ for all $k < n$. Structural induction follows the formation rules of an object. Well-founded induction works over any relation where infinite descent is impossible.

These are not separate tricks. They are variations of the same principle: prove the property at minimal cases, then prove it is preserved by construction.

Recursion and induction also appear in definitions of syntax. A formal language is often defined recursively. Terms are built from variables and function symbols. Formulas are built from atomic formulas using logical connectives and quantifiers.

To prove a property of all formulas, one uses induction on formula structure. Check atomic formulas, then show the property is preserved by negation, conjunction, implication, and quantification.

This is why recursion and induction are fundamental in logic, programming languages, and proof assistants.

They also appear in combinatorics. Many counting sequences are recursively defined. The Fibonacci numbers satisfy

and

The definition builds each term from previous terms. Induction proves identities about the sequence.

Recursion gives an object by rules. Induction gives a proof by the same rules. This pairing is one of the most important design patterns in mathematics.

A useful habit is to ask: how is the object built? The answer usually tells you how to prove things about it.

If the object is built by cases, prove by cases. If it is built step by step, prove by induction. If it is built from subobjects, prove by structural induction.

Recursion and induction make infinite families manageable. They reduce an infinite task to a finite base case plus a stable transition step.