Mathematical Induction

definitions
discrete-math
proof
induction

The principle of mathematical induction, the four-step shape every induction proof takes, and the extra care inequalities need. See sequences-and-summations for the summation manipulations these proofs run on, and proof-techniques for the other proof methods in the course.

Why it works

Let \(P(n)\) be a predicate written in terms of some integer \(n\). Suppose you know two statements are true:

  1. \(P(2)\)
  2. \(\forall k \in \mathbb{Z}\) with \(k \geq 2\), if \(P(k)\) then \(P(k+1)\)

Can you conclude \(P(5)\)? Yes — statement 2 is a general implication, so instantiate it repeatedly and apply modus ponens. The conclusion of one step is the premise of the next, which is what turns two facts into a chain (Figure 1).

Figure 1: Why those two statements are enough. The basis step pins one statement true; every hop after it is the same general implication used at one more value of \(k\), so each conclusion becomes the next premise. The panel writes one hop out in full — it is a single modus ponens, nothing more.

Nothing here is special to 5. \(P(5)\) is reached in three hops, but the chain never stops, so \(P(n)\) is true for each integer \(n \geq 2\).

Both statements are needed. Statement 2 alone gives nothing: an implication \(P(k) \to P(k+1)\) is true in three of the four rows of its truth table — including both rows where \(P(k)\) is false. Without the basis step pinning \(P\) true somewhere, the chain has nothing to start from and every link stays vacuously true while every \(P(n)\) stays false.

The shape of an induction proof

Four steps, and it is worth naming each one explicitly in the write-up so the reader can follow the argument:

  1. Define the predicate. Let \(P(n)\) denote (the statement, with \(n\) free).
  2. Basis step. Prove the predicate is true at the smallest value of \(n\) in the claim — evaluate the two sides separately and observe they agree.
  3. Inductive hypothesis. Suppose \(k\) is an integer at or above the basis value, and that the predicate is true for \(n = k\). Write out what \(P(k)\) actually says.
  4. Inductive step. Prove \(P(k+1)\) follows, i.e. \(\forall k \in \mathbb{Z}\) with \(k \geq\) (basis), if \(P(k)\) is true then \(P(k+1)\) is true. Start from the LHS of \(P(k+1)\), use the inductive hypothesis somewhere (say where), and arrive at the RHS of \(P(k+1)\).

Then conclude: therefore, by the principle of mathematical induction, … for each integer \(n \geq\) (basis).

One thing about the order. In the write-up, the inductive step’s goal — prove that \(\forall k \in \mathbb{Z}\) with \(k \geq\) (basis), if \(P(k)\) is true then \(P(k+1)\) is true — goes on the line above the inductive hypothesis, and the assumption is made underneath it: goal first, assumption second. The numbering above counts the four actions; the goal line itself is not numbered. Write the goal down, then assume, then work.

Worked example — a summation

Prove that for each integer \(n \geq 1\), \(\displaystyle\sum_{i=1}^{n} (3i+2) = \frac{3n^2 + 7n}{2}\).

Proof. Let \(P(n)\) denote the predicate \(\displaystyle\sum_{i=1}^{n} (3i+2) = \frac{3n^2+7n}{2}\).

Basis step. Prove the predicate is true for \(n = 1\).

LHS of \(P(1)\): \(\displaystyle\sum_{i=1}^{1}(3i+2) = 3 \cdot 1 + 2 = 5\). RHS of \(P(1)\): \(\dfrac{3(1^2) + 7(1)}{2} = \dfrac{3+7}{2} = 5\). Therefore \(P(1)\) is true.

Inductive step. Prove that \(\forall k \in \mathbb{Z}\) with \(k \geq 1\), if \(P(k)\) is true then \(P(k+1)\) is true.

Inductive hypothesis: suppose \(k \geq 1\) is an integer and the predicate is true for \(n = k\) — that is, \(\displaystyle\sum_{i=1}^{k}(3i+2) = \frac{3k^2+7k}{2}\).

LHS of \(P(k+1)\):

\[\sum_{i=1}^{k+1}(3i+2) = \sum_{i=1}^{k}(3i+2) + \big(3(k+1)+2\big)\] \[= \frac{3k^2+7k}{2} + 3k + 5 \qquad \text{(by the inductive hypothesis } P(k)\text{)}\] \[= \frac{3k^2 + 13k + 10}{2} = \frac{3(k^2+2k+1) + 7k + 7}{2} = \frac{3(k+1)^2 + 7(k+1)}{2}\]

which is the RHS of \(P(k+1)\).

Therefore, by the principle of mathematical induction, \(\displaystyle\sum_{i=1}^{n}(3i+2) = \frac{3n^2+7n}{2}\) for each integer \(n \geq 1\).

The move at the first line is splitting off the last term (see sequences-and-summations) — that is what exposes the \(P(k)\) sum so the hypothesis can be applied to it. Figure 2 tracks that one expression through the chain.

Figure 2: Where the inductive hypothesis actually enters. Splitting off the last term turns the LHS of \(P(k+1)\) into the LHS of \(P(k)\), plus one more term; the hypothesis is then spent exactly once, swapping that sum for its closed form; everything below is algebra. The shading follows that one expression from line to line.

Before starting the chain, write down what the RHS of \(P(k+1)\) actually is — here \(\frac{3(k+1)^2 + 7(k+1)}{2}\). Without it you are simplifying with no idea what counts as finished; with it, the last algebraic step is obvious, because you already know the shape you are steering the numerator into.

Induction with inequalities

Be careful when manipulating inequalities. The rules that hold:

Given Conclusion
\(a < b\) \(a + x < b + x\), regardless of the sign of \(x\)
\(a < b\), \(x\) positive \(ax < bx\)
\(a < b\), \(x\) negative \(ax > bx\) — the direction flips
\(a < b\), \(x\) zero \(ax = bx\)
\(a < b\) and \(x < y\) \(a + x < b + y\)
\(a < b\) and \(x > y\) nothing can be concluded about \(a + x\)

All of these still hold with \(<\) and \(>\) replaced by \(\leq\) and \(\geq\).

Worked example — \(n^2 < 2^n\)

Prove that for each integer \(n \geq 5\), \(n^2 < 2^n\).

Proof. Let \(P(n)\) be the predicate \(n^2 < 2^n\).

Basis step. Consider \(n = 5\). Then \(n^2 = 25\) and \(2^n = 32\). Since \(25 < 32\), \(P(5)\) is true.

Inductive hypothesis. Suppose \(k \geq 5\) is an integer and \(P(k)\) is true. Thus \(k^2 < 2^k\), and hence \(2k^2 < 2 \cdot 2^k\).

Inductive step. Consider \(n = k+1\); the goal is \((k+1)^2 < 2^{k+1} = 2 \cdot 2^k\).

\[(k+1)^2 = k^2 + 2k + 1 < k^2 + 2k + k = k^2 + 3k < k^2 + k^2 = 2k^2 < 2(2^k) = 2^{k+1}\]

The first inequality uses \(1 < k\) (since \(k \geq 5\)); the second uses \(3k < k \cdot k\), which holds because \(5 \leq k\); the last uses the inductive hypothesis. Thus \(P(k+1)\) is true.

Therefore, by PMI, for each integer \(n \geq 5\), \(n^2 < 2^n\).

The pattern for an inequality is a chain: start at the LHS of \(P(k+1)\) and relax it one step at a time — each step justified by a rule from the table or by the inductive hypothesis — until it reaches the RHS of \(P(k+1)\). Every step must be an inequality in the same direction, or the chain says nothing.

The inductive step must hold at every \(k\)

Including the first one. An inductive step that is sound for all large \(k\) but fails at the basis value leaves a gap the chain cannot cross, and the induction proves nothing beyond the basis case — even though every individual line of the argument can look correct.

The classic demonstration is the ‘proof’ that all numbers are equal, whose inductive step is valid for every \(k \geq 2\) and false at \(k = 1\); it is picked apart in 2026-08-31-recursive-definitions. When checking an induction proof, run the inductive step at the smallest \(k\) it claims to cover and see whether it still says anything.

Strong induction

When the inductive step needs more than just the immediately preceding case — typically because a recurrence reaches back several terms, or because the step splits a number into two smaller ones it cannot control — ordinary induction is not enough. See strong-induction-and-the-well-ordering-principle for the stronger form, how many base cases it demands, and the well-ordering principle it is equivalent to.

See also