2.9 Mathematical induction

Concept of mathematical induction

Mathematical induction is a proof technique for establishing that a statement holds for every natural number. Instead of checking infinitely many cases one by one (which is impossible), you prove just two things and let logic handle the rest. This technique shows up constantly in proofs about sums, divisibility, inequalities, and algorithm correctness.

The core idea: show the statement is true for a starting value, then show that whenever it's true for one value, it must be true for the next. Once both pieces are in place, the truth propagates forward through all natural numbers.

Principle of mathematical induction

Mathematical induction works by proving two components:

1. Base case: Show the statement holds for the smallest value (usually $n = 0$ or $n = 1$).
2. Inductive step: Show that if the statement is true for some arbitrary natural number $k$, then it must also be true for $k + 1$.

From these two pieces, you can conclude the statement is true for all natural numbers. The base case gets things started, and the inductive step carries the truth forward from each number to the next.

The validity of this reasoning rests on the well-ordering principle: every non-empty set of natural numbers has a least element. If the statement failed somewhere, there would be a smallest counterexample, but the inductive step makes that impossible.

Strong induction vs. weak induction

• Weak induction assumes the statement is true for a single value $k$ and uses that to prove it for $k + 1$.
• Strong induction assumes the statement is true for all values from the base case up through $k$, then proves it for $k + 1$.

Strong induction is especially useful when proving $P(k+1)$ requires information from more than just the immediately preceding case. For example, proofs involving Fibonacci-type recurrences (where each term depends on the two previous terms) often need strong induction.

Despite the names, the two forms are logically equivalent. Any proof using strong induction can be rewritten using weak induction, and vice versa. The difference is purely about convenience.

Well-ordering principle connection

The well-ordering principle states that every non-empty set of positive integers contains a least element. This is logically equivalent to the principle of mathematical induction.

Here's why that matters: if you want to prove a statement $P(n)$ for all natural numbers, you can argue by contradiction. Suppose the set of counterexamples is non-empty. By well-ordering, there's a smallest counterexample. Then you show that smallest counterexample can't actually exist (because the base case and inductive step rule it out). This "minimal counterexample" approach is an alternative proof strategy that draws directly on well-ordering.

Structure of induction proofs

A well-written induction proof has three clearly labeled parts. Here's how to build one:

Base case establishment

1. Identify the starting value for your statement (usually $n = 0$ or $n = 1$).
2. Substitute that value into both sides of the statement.
3. Verify directly (through computation or simple logic) that the statement holds.

This step is often short, but skipping it or getting it wrong invalidates the entire proof. Without a verified starting point, the inductive step has nothing to build on.

Some proofs require multiple base cases. For instance, if your inductive step for $P(k+1)$ relies on both $P(k)$ and $P(k-1)$, you'll need to verify both $P(0)$ and $P(1)$ separately.

Inductive hypothesis formulation

State your assumption clearly: "Assume $P(k)$ is true for some arbitrary natural number $k$." In formal notation, you're assuming $P(k)$ holds and will use it to derive $P(k+1)$.

For strong induction, the hypothesis is broader: "Assume $P(j)$ is true for all $j$ with $1 \leq j \leq k$."

The hypothesis must match the original proposition exactly. If your statement involves a sum formula, write out what that formula looks like when $n = k$. Being precise here prevents errors in the next step.

Inductive step demonstration

This is where the real work happens. You need to show that $P(k) \Rightarrow P(k+1)$.

1. Write out what $P(k+1)$ says (this is your goal).
2. Start from $P(k+1)$'s left-hand side or setup, and manipulate it.
3. Find a place to substitute in the inductive hypothesis $P(k)$.
4. Continue simplifying until you arrive at what $P(k+1)$ claims.

The key challenge is connecting $P(k)$ to $P(k+1)$. This often requires algebraic manipulation, factoring, or a clever rewriting of expressions. If you can't find the connection, consider whether strong induction or a different proof technique might work better.

Types of induction

Simple (weak) induction

This is the standard form described above. You assume $P(k)$ and prove $P(k+1)$. It works well when each case depends only on the immediately preceding one.

Most textbook induction proofs use this form: sum formulas, basic divisibility results, and straightforward inequalities.

Complete (strong) induction

Also called course-of-values induction. You assume $P(j)$ holds for every $j \leq k$, then prove $P(k+1)$.

This is the right tool when:

• The recurrence defining your sequence looks back more than one step
• You need to break $k+1$ into smaller pieces (e.g., proving every integer $\geq 2$ has a prime factorization)
• The "previous case" you need isn't always $k$ but depends on the situation

Structural induction

Structural induction extends the idea beyond numbers to recursively defined structures like trees, lists, or logical formulas.

• Base case: Prove the property for the simplest structures (e.g., an empty list, a single node).
• Inductive step: Assume the property holds for the sub-components, then prove it holds for the structure built from those components.

This form is heavily used in computer science and mathematical logic. The reasoning mirrors the recursive definition of the structure itself.

Common applications

Summation formulas

Induction is the standard way to prove closed-form expressions for sums. A classic example:

Prove $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ for all $n \geq 1$.

1. Base case ($n = 1$): Left side is $1$. Right side is $\frac{1 \cdot 2}{2} = 1$. ✓
2. Inductive hypothesis: Assume $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$.
3. Inductive step: Show it holds for $k + 1$:

$\sum_{i=1}^{k+1} i = \left(\sum_{i=1}^{k} i\right) + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$

That's exactly the formula with $n = k+1$. ✓

This same pattern applies to geometric sums, sums of squares, and binomial identities.

Divisibility proofs

Induction can show divisibility properties hold for all natural numbers. For example:

Prove $3^n - 1$ is divisible by $2$ for all $n \geq 1$.

1. Base case ($n = 1$): $3^1 - 1 = 2$, which is divisible by $2$. ✓

2. Inductive hypothesis: Assume $2 \mid (3^k - 1)$, meaning $3^k - 1 = 2m$ for some integer $m$.

3. Inductive step: $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(2m + 1) - 1 = 6m + 2 = 2(3m + 1)$. This is divisible by $2$. ✓

The inductive step often involves factoring or rewriting expressions to expose the divisibility, sometimes using modular arithmetic.

Inequality proofs

Induction proves inequalities hold across all natural numbers (or from some starting point). For example, proving $2^n > n$ for all $n \geq 1$, or $n! > 2^n$ for all $n \geq 4$.

The inductive step for inequalities typically requires you to show that the "gap" between the two sides is preserved (or grows) when moving from $k$ to $k+1$. This sometimes takes careful algebraic work or bounding arguments.

Advanced induction techniques

Two-base induction

Some statements need two (or more) verified base cases before the inductive step can take over. This happens when the inductive step for $P(k+1)$ relies on both $P(k)$ and $P(k-1)$.

The Fibonacci sequence is a natural example: since $F_{n+1} = F_n + F_{n-1}$, proving properties of Fibonacci numbers often requires checking both $F_1$ and $F_2$ as base cases. This generalizes to multi-base induction for recurrences that look back further.

Backward induction

Backward induction starts from a later case and reasons toward earlier ones. It's widely used in game theory (proving optimal strategies in finite games) and dynamic programming (solving optimization problems by working from the end state backward).

This technique is distinct from standard forward induction but still relies on the well-ordering of the natural numbers to ensure the reasoning terminates.

Infinite descent

Developed by Pierre de Fermat, infinite descent proves a statement by contradiction: assume a counterexample exists, then show it implies a smaller counterexample must also exist. Repeating this argument produces an infinite descending sequence of positive integers, which contradicts the well-ordering principle.

Fermat used this method to prove that there is no right triangle with integer sides whose area is a perfect square. It remains a powerful technique in number theory, especially for showing certain Diophantine equations have no solutions.

Limitations and pitfalls

Common mistakes in induction proofs

• Skipping or botching the base case. The classic "all horses are the same color" fallacy results from a flawed base case. Always verify it carefully.
• Circular reasoning in the inductive step. If you assume $P(k+1)$ while trying to prove $P(k+1)$, the proof is invalid. You must start from $P(k)$ and derive $P(k+1)$.
• Using weak induction when strong induction is needed. If your argument for $P(k+1)$ requires more than just $P(k)$, switch to strong induction.
• Imprecise inductive hypothesis. State exactly what you're assuming. Vague hypotheses lead to gaps in the proof.

When induction doesn't apply

Induction works for statements indexed by natural numbers (or recursively defined structures). It's not the right tool for:

• Statements about real numbers or continuous domains
• Problems where no natural ordering or recursive structure exists
• Situations where a direct proof, contradiction, or counterexample is simpler and more appropriate

Choosing the right proof technique is itself an important mathematical skill.

Induction in computer science

Algorithm correctness proofs

Induction is the primary method for proving algorithms work correctly on all valid inputs. For iterative algorithms, you prove a loop invariant: a statement that's true before the loop starts, preserved by each iteration, and implies correctness when the loop terminates. For recursive algorithms, structural induction mirrors the recursive calls directly.

Data structure properties

Recursively defined data structures (linked lists, binary trees, graphs) have properties that are naturally proved by structural induction. For example, you can prove that a balanced binary search tree with $n$ nodes has height $O(\log n)$ by inducting on the structure of the tree.

Program verification

Formal program verification combines induction with logic to prove programs behave correctly. Loop invariants handle iterative code, structural induction handles recursive functions, and well-founded induction (induction over a quantity that strictly decreases) proves that programs terminate. These techniques are critical in safety-critical systems like medical devices and aviation software.

Historical development

Origins

The roots of inductive reasoning trace back to ancient Greek mathematics, but the technique was first explicitly used by Francesco Maurolico in 1575 to prove properties of odd numbers. Blaise Pascal refined and popularized the method in the 17th century through his work on the arithmetic triangle (Pascal's triangle).

Key contributors

• Pierre de Fermat developed infinite descent as a proof technique in number theory.
• Jakob Bernoulli applied induction systematically in probability.
• Richard Dedekind formalized induction within his axiomatization of the natural numbers (1888).
• Giuseppe Peano included induction as one of his five axioms for arithmetic (1889).

Modern developments

Induction has expanded well beyond its original scope:

• Transfinite induction extends the principle to ordinal numbers beyond the natural numbers.
• Structural induction became a standard tool in computer science and programming language theory.
• Proof assistants (like Coq and Isabelle) automate inductive reasoning, enabling machine-verified proofs.

Relationship to other concepts

Induction vs. deduction

Don't confuse mathematical induction with inductive reasoning in science. Scientific induction generalizes from observed patterns ("the sun has risen every day, so it will rise tomorrow"). Mathematical induction is a form of deductive proof: once the base case and inductive step are established, the conclusion follows with certainty for all natural numbers.

Connection to recursion

Induction and recursion are two sides of the same coin. A recursive definition builds objects up from base cases using a rule; an inductive proof verifies properties by checking the base case and showing the rule preserves the property. If you understand recursion, you already have strong intuition for how induction works.

Role in axiomatic systems

The induction principle is one of the Peano axioms, which formally define the natural numbers. Without it, you couldn't distinguish the natural numbers from other structures that satisfy the remaining axioms. Induction is what gives the natural numbers their characteristic "reachability": every natural number can be reached by starting at $0$ and repeatedly adding $1$.