05 Induction and Recursion

A structured guide to proving statements about natural numbers and recursively generated objects, defining recursive functions and sets, and selecting the proof method that matches a construction.

Ordinary Induction

Induction and recursion address related but distinct tasks. proves that a property survives every permitted step from simpler cases to more complex cases. Recursion defines an object or function by referring to smaller instances of the same type.

For a proposition $P(n)$ about integers $n\geq n_0$ , an ordinary induction proof has two essential parts:

Base case: Show that $P(n_0)$ is true.
Inductive step: Choose an arbitrary $k\geq n_0$ and show that $P(k)$ implies $P(k+1)$ .

The assumption $P(k)$ is the . The index $k$ must be arbitrary; proving one numerical instance does not establish the general implication.

Worked algebraic pattern

To prove

1+2+\cdots+n=\frac{n(n+1)}{2}

for every $n\geq 1$ , the base case is

1=\frac{1(1+1)}{2}.

For the inductive step, assume

1+2+\cdots+k=\frac{k(k+1)}{2}.

Then

\begin{aligned} 1+2+\cdots+k+(k+1) &=\frac{k(k+1)}{2}+(k+1)\\ &=\frac{(k+1)(k+2)}{2}. \end{aligned}

This is the desired formula with $n=k+1$ .

Common checks

Establish both the base case and the inductive step.
Assume $P(k)$ , not $P(k+1)$ .
Make clear that $k$ is arbitrary in the required range.
Ensure that the is strong enough for the argument.

Takeaway: Ordinary induction works when the next case follows naturally from the immediately preceding case.

and Its Uses

allows the proof of $P(k+1)$ to use every earlier case:

P(n_0),P(n_0+1),\ldots,P(k).

The base case is still required, and the conclusion is still that $P(n)$ holds for every $n\geq n_0$ . The difference lies only in the hypotheses available during the inductive step.

Prime-factor example

Consider the claim that every integer greater than $1$ is either prime or has a prime factor. The base case $n=2$ holds because $2$ is prime.

For the inductive step, assume the claim holds for every integer from $2$ through $k$ , where $k\geq 2$ . Consider $k+1$ :

If $k+1$ is prime, it has a prime factor, namely itself.
If $k+1$ is composite, write $k+1=ab$ , where $2\leq a,b<k+1$ . Since $a$ is an earlier integer, the hypothesis gives a prime factor of $a$ . That prime also divides $k+1$ .

The smaller factor may be much less than $k$ , so ordinary induction would not directly provide the needed statement about it.

Choosing between ordinary and

Use ordinary induction when the case of size $k+1$ is built directly from the case of size $k$ . Use when the argument needs one or more earlier cases whose indices are not necessarily $k$ .

Takeaway: does not change the conclusion; it broadens the assumptions available to prove the next case.

Well-Ordering and Minimal Counterexamples

The states that every nonempty subset of the nonnegative integers has a least element. A corresponding version can be stated for the positive integers.

This principle leads to proof by minimal counterexample. To prove a proposition $P(n)$ for all integers in a specified range:

Assume that at least one counterexample exists.
Let $m$ be the least counterexample.
Because $m$ is least, every smaller integer in the range satisfies the proposition.
Use those smaller cases to show that $P(m)$ must also be true.
This contradiction shows that no counterexample exists.

The domain matters. The set of all integers has no least element, and the positive rational numbers need not have a least element under their usual ordering. Thus, the principle cannot be applied without checking that the relevant set is a nonempty subset of the appropriate integer domain.

For the natural numbers, ordinary induction, , and the are logically equivalent: a proof using one can be reformulated using either of the others.

Takeaway: Use well-ordering when the least possible failure is easier to analyze than a direct inductive step.

Recursive Definitions of Functions and Sets

A describes an object through smaller instances of the same kind. A well-formed definition generally contains three components:

Base clause(s): Specify the initial object or value.
Recursive clause(s): Explain how to construct new objects or values from previously defined ones.
: State that only objects generated by these clauses belong to the defined collection.

Recursive functions

The factorial function is defined by

0!=1, \qquad (n+1)!=(n+1)n!\quad(n\geq 0).

The base value starts the computation, and the recursive clause reduces the next value to a smaller one.

The Fibonacci sequence requires two base cases because its rule refers to two preceding values:

F_0=0, \qquad F_1=1, \qquad F_n=F_{n-1}+F_{n-2}\quad(n\geq 2).

A is therefore both a mathematical specification and, in many cases, a direct procedure for computing values.

Recursive sets

The set of balanced-parenthesis strings can be generated by these rules:

The empty string $\varepsilon$ is balanced.
If $w$ is balanced, then $(w)$ is balanced.
If $u$ and $v$ are balanced, then their concatenation $uv$ is balanced.
No other strings are balanced.

The last rule is the closure or minimality requirement. It prevents unrelated strings from entering the set.

Takeaway: A must state where construction begins, how it proceeds, and which objects are excluded.

on Recursive Objects

follows the constructors in a rather than counting through the integers. Its proof pattern is:

Basis: Prove the property for every object introduced by a base clause.
Inductive cases: For each recursive construction rule, assume the property for the immediate component objects and prove it for the newly constructed object.
Conclusion: State that the property holds for every object generated by the definition.

Binary-tree example

Define a binary tree recursively:

A single vertex is a binary tree.
If $T_1$ and $T_2$ are binary trees, a new root with left subtree $T_1$ and right subtree $T_2$ is a binary tree.

Let $L(T)$ denote the number of leaves and $I(T)$ the number of internal vertices. We prove

L(T)=I(T)+1.

For the basis, a single vertex is a leaf and has no internal vertices, so

L(T)=1=0+1.

For the recursive case, assume the identity holds for $T_1$ and $T_2$ . The new tree satisfies

L(T)=L(T_1)+L(T_2)

and

I(T)=I(T_1)+I(T_2)+1.

Applying the induction hypotheses gives

\begin{aligned} L(T)&=(I(T_1)+1)+(I(T_2)+1)\\ &=I(T_1)+I(T_2)+2\\ &=I(T)+1. \end{aligned}

Thus the identity holds for every binary tree generated by the definition.

The same approach applies to strings, formulas, algebraic expressions, and other structures whose formation rules are explicit.

Takeaway: Match each inductive case to a constructor; the proof must cover every way an object can be generated.

Selecting the Right Method

The proof method should mirror the way the relevant objects are built.

Use ordinary induction when the case of size $k+1$ follows from the case of size $k$ .
Use when the case of size $k+1$ depends on several earlier cases or on an arbitrarily smaller case.
Use well-ordering when selecting and analyzing a least counterexample is natural.
Use a to specify functions, sets, or objects from smaller instances.
Use when objects are generated by constructors such as tree-building, concatenation, or formula formation.

All of these methods express a common idea: a finite object or natural number is generated from simpler predecessors, and a property that survives every permitted construction holds throughout the generated collection.

A practical checklist

Identify the objects or integers covered by the claim.
Identify how a new case is generated from earlier cases.
Choose the method whose hypotheses match that construction.
State every base clause or base case.
Prove every required inductive or structural case.
Check that the conclusion covers exactly the intended domain.

Final takeaway: The strongest proof is not necessarily the one with the strongest hypothesis. It is the one whose structure matches the way the objects or cases are constructed.