Tutorials › Real Analysis › Mathematical Induction

Home  /  Tutorials  /  Induction and Elementary Proofs

Induction and Elementary Proofs · Tutorial 126 of 1000

Mathematical Induction

Understand how a verified starting case and a valid successor step establish a statement for an entire sequence of integers.

Beginner 9 min read

What You'll Learn

  • Identify the base case, inductive hypothesis, and inductive step in a proof
  • State and justify the principle of mathematical induction
  • Prove finite-sum identities by induction
  • Use induction to establish inequalities for all nonnegative integers
  • Prove divisibility claims by tracking the inductive hypothesis
  • Recognize why a few verified cases do not prove a universal statement

From One Case to Every Case

Many statements in analysis concern every integer in an infinite range: a formula for a sum, an inequality for all sufficiently large powers, or a divisibility property that holds at every stage. Checking the first several cases can suggest that a claim is true, but it cannot cover infinitely many cases. Mathematical induction gives a precise way to do that: verify a starting case, then show that whenever the claim holds at one stage, it also holds at the next.

The previous tutorial emphasized beginning with the assumptions of a statement and justifying each step. Induction uses the same discipline, but organizes the proof around a sequence of related claims. The starting case anchors the argument. The inductive step establishes the rule that carries truth forward. Both parts are necessary.

The Principle of Mathematical Induction

Write \(\mathbb{N}_0=\{0,1,2,\ldots\}\) for the nonnegative integers. A statement \(P(n)\) is a claim whose truth can depend on \(n\in\mathbb{N}_0\). To prove it for every nonnegative integer, induction asks us to establish \(P(0)\) and to show that \(P(n)\) implies \(P(n+1)\) for each \(n\in\mathbb{N}_0\).

Theorem (Principle of Mathematical Induction). Let \(P(n)\) be a statement for each \(n\in\mathbb{N}_0\). Suppose \(P(0)\) is true, and suppose that for every \(n\in\mathbb{N}_0\), if \(P(n)\) is true, then \(P(n+1)\) is true. Then \(P(n)\) is true for every \(n\in\mathbb{N}_0\).

Proof. Suppose the conclusion were false. Then the set \(A=\{n\in\mathbb{N}_0:P(n)\text{ is false}\}\) would be nonempty. By the least-element property of the nonnegative integers, \(A\) has a least element, say \(m\). Since \(P(0)\) is true, \(m\ne0\), so \(m\ge1\). Therefore \(m-1\in\mathbb{N}_0\). By the minimality of \(m\), \(m-1\notin A\), which means \(P(m-1)\) is true. The inductive step then implies that \(P(m)\) is true, contradicting \(m\in A\). Thus \(A\) is empty, and \(P(n)\) is true for every \(n\in\mathbb{N}_0\). \(\square\)

The same principle starts at any chosen integer \(m\), not only at zero. The starting value must be included in the claim, and the step must apply at every integer at or above that starting value.

Corollary (Induction Starting at \(m\)). Let \(m\in\mathbb{N}_0\). Suppose \(P(m)\) is true and, for every integer \(n\ge m\), \(P(n)\) implies \(P(n+1)\). Then \(P(n)\) is true for every integer \(n\ge m\).

Proof. Define \(Q(k)=P(m+k)\) for \(k\in\mathbb{N}_0\). We have \(Q(0)=P(m)\), so \(Q(0)\) is true. If \(Q(k)\) is true, then \(P(m+k)\) is true. Since \(m+k\ge m\), the assumed step gives \(P(m+k+1)\), which is \(Q(k+1)\). The Principle of Mathematical Induction applied to \(Q\) gives \(Q(k)\) for every \(k\in\mathbb{N}_0\). Equivalently, \(P(n)\) holds for every \(n\ge m\). \(\square\)

How to Write an Induction Proof

An induction proof is a direct proof of two separate obligations. First, verify the base case by substituting the starting integer into the claim. Second, take an arbitrary integer \(n\) in the range and assume \(P(n)\); this assumption is the inductive hypothesis. Using it, prove \(P(n+1)\). The hypothesis is temporary and is used only to establish the next case.

1
State the claim.
Specify exactly what \(P(n)\) says and the range of integers under consideration.
2
Check the base case.
Verify the claim at the first integer in the range, with the relevant expressions evaluated there.
3
Assume one case.
Fix an arbitrary \(n\) in the range and assume \(P(n)\) is true.
4
Prove the next case.
Use the inductive hypothesis and valid algebra or inequalities to establish \(P(n+1)\).
5
Conclude the full range.
Invoke the Principle of Mathematical Induction, or its version starting at \(m\).

Worked Examples

Worked Example: A Sum of Consecutive Odd Integers

For every \(n\in\mathbb{N}_0\), prove

$$ \sum_{k=1}^{n}(2k-1)=n^2. $$

When \(n=0\), the sum has no terms and is defined to be \(0\). Thus the left side is \(0\), while the right side is \(0^2=0\), so the base case holds. Now assume for an arbitrary \(n\in\mathbb{N}_0\) that

$$ \sum_{k=1}^{n}(2k-1)=n^2. $$

The sum through \(n+1\) is the sum through \(n\), followed by its next term. Using the inductive hypothesis,

$$ \sum_{k=1}^{n+1}(2k-1) =\sum_{k=1}^{n}(2k-1)+\bigl(2(n+1)-1\bigr) =n^2+2n+1 =(n+1)^2. $$

This is the required formula with \(n+1\) in place of \(n\). Induction proves the identity for every \(n\in\mathbb{N}_0\). For example, when \(n=4\), the sum is \(1+3+5+7=16=4^2\), consistent with the general result.

Worked Example: A Finite Geometric Sum

Fix a real number \(r\ne1\). We prove for every \(n\in\mathbb{N}_0\) that

$$ 1+r+r^2+\cdots+r^n=\frac{r^{n+1}-1}{r-1}. $$

At \(n=0\), the left side is \(1\). The right side is \((r-1)/(r-1)=1\), since \(r\ne1\), so the base case holds. Assume the formula holds for some \(n\in\mathbb{N}_0\). Adding the next term \(r^{n+1}\) gives

$$ 1+r+\cdots+r^n+r^{n+1} =\frac{r^{n+1}-1}{r-1}+r^{n+1} =\frac{r^{n+1}-1+r^{n+1}(r-1)}{r-1} =\frac{r^{n+2}-1}{r-1}. $$

The final expression is the stated formula at \(n+1\). Therefore the formula holds for all nonnegative integers. As a check, with \(r=2\) and \(n=3\), the sum is \(1+2+4+8=15\), and the formula gives \((2^4-1)/(2-1)=15\).

Worked Example: An Inequality for Every Nonnegative Integer

We prove that \(3^n\ge 2n+1\) for every \(n\in\mathbb{N}_0\). At \(n=0\), both sides equal \(1\), so the base case is true. Suppose for an arbitrary \(n\in\mathbb{N}_0\) that \(3^n\ge2n+1\). Since \(3>0\), multiplying this inequality by \(3\) preserves its direction, giving

$$ 3^{n+1}=3\cdot3^n\ge3(2n+1)=6n+3. $$

For \(n\ge0\), the difference between this lower bound and the desired right side is

$$ (6n+3)-\bigl(2(n+1)+1\bigr) =6n+3-(2n+3) =4n\ge0. $$

Hence \(6n+3\ge2(n+1)+1\). Chaining the two non-strict inequalities gives \(3^{n+1}\ge2(n+1)+1\), as required. Induction proves the claim for every \(n\in\mathbb{N}_0\). For \(n=2\), this reads \(9\ge5\), and direct substitution confirms the particular case.

Worked Example: A Divisibility Statement

For every \(n\in\mathbb{N}_0\), \(7\) divides \(8^n-1\). Here “\(7\) divides an integer \(a\)” means that \(a=7q\) for some integer \(q\). At \(n=0\), \(8^0-1=1-1=0=7\cdot0\), so the base case holds. Suppose \(8^n-1=7q\) for some integer \(q\). Then

$$ 8^{n+1}-1 =8\cdot8^n-1 =8(8^n-1)+7 =8(7q)+7 =7(8q+1). $$

Because \(q\) is an integer, \(8q+1\) is an integer. Thus \(7\) divides \(8^{n+1}-1\), proving the inductive step. Induction establishes the divisibility claim for every \(n\in\mathbb{N}_0\). For example, when \(n=2\), \(8^2-1=63=7\cdot9\).

Why Both Parts Matter

The inductive step alone does not establish that any case is true. For example, a statement could be false at every integer while the implication from one case to the next still holds. The base case supplies the initial truth from which the step can proceed. Conversely, checking several initial cases without proving the step provides no guarantee about later cases. Induction is not a pattern-recognition shortcut; it is a proof that links every successive case to a verified starting point.

A frequent error is to assume the very conclusion being proved. In the inductive step, assume only \(P(n)\), for one arbitrary \(n\), and then derive \(P(n+1)\). Do not assume \(P(n+1)\), and do not treat the truth of several examples as the inductive hypothesis. Another error is to omit the range: if the claim starts at \(n=3\), the base case is \(P(3)\), and the step must take \(n\ge3\) to \(n+1\).

Induction applies to statements indexed by consecutive integers, not directly to all real numbers. An induction proof of a formula for \(n\in\mathbb{N}_0\) does not by itself establish that formula for a real input \(x\). Its strength is precisely the connection between discrete stages: once the first stage is secure and every stage passes the claim to its successor, the Principle of Mathematical Induction guarantees all stages in the range.

Key takeaway. To prove a claim for every integer from a specified starting point onward, verify the first case and prove that an arbitrary true case forces the next one. The base case anchors the chain; the inductive step carries it forward.

Check Your Understanding

For each question, identify how the base case and inductive step contribute to a complete induction proof.

  1. In the sum-of-odd-integers example, why is the sum at \(n=0\) equal to \(0\), and what is the value of the right side?
  2. For the geometric-sum formula, where is the condition \(r\ne1\) needed in the base case and in the inductive step?
  3. In the proof that \(3^n\ge2n+1\), why does multiplying by \(3\) preserve the inequality direction?
  4. State the inductive hypothesis used to prove that \(7\) divides \(8^n-1\), and explain why \(8q+1\) is an integer.
  5. What additional fact, beyond checking \(P(0)\), is required to use induction to prove \(P(n)\) for every \(n\in\mathbb{N}_0\)?

Previous

Next

Back to Tutorials