Induction is the standard proof technique for objects built in stages. Recursion is the matching construction technique. Together they describe how to define, compute, and prove statements about natural numbers, lists, trees, syntax, algorithms, and other generated structures.

The simplest form is mathematical induction on natural numbers.

To prove a statement $P(n)$ for every natural number $n$, prove two things.

First, prove the base case:

Second, prove the induction step:

Once both are established, the conclusion follows:

The idea is that the base case starts the chain, and the induction step carries truth from one stage to the next.

For example, prove that

for every integer $n \geq 1$.

For $n=1$, the left side is $1$, and the right side is

So the base case holds.

Now assume the formula holds for some $n$:

Then

$$ 1 + 2 + \cdots + n + (n+1)

\frac{n(n+1)}{2} + (n+1). $$

Factor the right side:

$$ \frac{n(n+1)}{2} + (n+1)

(n+1)\left(\frac{n}{2}+1\right)

\frac{(n+1)(n+2)}{2}. $$

This is the desired formula with $n+1$ in place of $n$. Therefore, the formula holds for all $n \geq 1$.

The temporary assumption that $P(n)$ holds is called the induction hypothesis. It must be used only to prove the next case. It is not an assumption that the result is already known for all values.

Induction works because the natural numbers are generated from a starting point by repeated application of a successor operation. The proof mirrors the construction of the object.

Recursion is the construction side of the same idea. A recursively defined object is specified by base data and a rule for producing larger cases.

For example, the factorial function is defined by

and

The definition tells us how to compute the value at each stage from earlier values. Induction tells us how to prove properties of those values.

Strong induction is a variant where the induction step may use all earlier cases. To prove $P(n)$ for all $n$, one proves that if $P(k)$ holds for every $k < n$, then $P(n)$ holds.

This is useful when the next case depends on more than the immediately previous case.

For example, many divisibility and factorization arguments use strong induction because a number may be reduced to a smaller factor that is not exactly one less.

Structural induction extends the same idea beyond natural numbers. If objects are built by constructors, then a proof follows those constructors.

For lists, one proves a property for the empty list, then proves that if it holds for a list $L$, it also holds for a list formed by adding one element to $L$.

For trees, one proves the property for leaves, then proves that if it holds for subtrees, it holds for the tree built from them.

For formal syntax, one proves the property for atomic expressions, then proves that each formation rule preserves the property.

This makes induction one of the main proof techniques in logic and computer science. Many theorems about programs, grammars, formulas, and data structures are structural induction arguments.

The main discipline in induction is choosing the right statement. Sometimes the desired claim is too weak to prove by induction because the step needs a stronger hypothesis. In that case, the solution is to strengthen the induction statement.

For example, a theorem about an algorithm may need an invariant: a property preserved at every stage of execution. The invariant may be stronger than the final result, but it makes the induction step possible.

A common failure is proving the base case and then assuming the conclusion instead of proving the step. The induction step must show that the property is preserved from one stage to the next.

Another common failure is using induction over the wrong parameter. The parameter should measure the construction of the object: size, length, depth, number of steps, or natural-number index.

Induction is effective when the object has a recursive structure. It turns an infinite family of claims into a finite proof pattern: start correctly, then preserve correctness at every step.

Recursion builds objects. Induction proves properties of the objects so built.