This is a beta course, so its structure, chapters, and examples may continue to change.

The Principle of Mathematical Induction

Mathematical induction is a rigorous proof method, specially used to prove propositions related to positive integers. Understanding its principle gives you a powerful proof tool.

The Basic Principle

The principle of mathematical induction

To prove that the proposition $P(n)$ holds for all positive integers $n \geq n_0$ , it suffices to prove:

The base case: $P(n_0)$ holds
The inductive step: assuming $P(k)$ holds (the inductive hypothesis), prove that $P(k+1)$ also holds

Core idea: if the first domino falls, and each falling domino knocks down the next one, then all the dominoes will fall.

The Steps of the Proof

The standard steps for proving a proposition using mathematical induction:

Step 1: The Base Case

Verify that the proposition holds for the initial value $n = n_0$ (usually 1).

Example: prove that $P(1)$ holds

Step 2: The Inductive Hypothesis

Assume that the proposition holds for $n = k$ ( $k \geq n_0$ ).

Example: assume $P(k)$ holds

Step 3: The Inductive Step

On the basis of the inductive hypothesis, prove that the proposition also holds for $n = k+1$ .

Example: using the fact that $P(k)$ holds, prove that $P(k+1)$ holds

Step 4: Conclusion

By the principle of mathematical induction, the proposition holds for all $n \geq n_0$ .

Why is mathematical induction valid?

The validity of mathematical induction rests on the well-ordering property of the natural numbers: every nonempty set of natural numbers has a least element.

Suppose the proposition $P(n)$ does not hold for all $n \geq n_0$ . Then there exists a least $m > n_0$ such that $P(m)$ does not hold.

But:

$P(n_0)$ holds (the base case)
$P(m-1)$ holds (because $m$ is the least counterexample)
By the inductive step, $P(m)$ should hold

This is a contradiction! So the proposition holds for all $n \geq n_0$ .

This is why both steps are indispensable:

Without the base case, the first domino does not fall
Without the inductive step, there is no chain reaction among the dominoes

Simple Examples

Example 1: Proving a Summation Formula

Proposition: prove that $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ for all positive integers $n$ .

Proof:

Base case: when $n = 1$ , $\text{left side} = 1, \quad \text{right side} = \frac{1 \times 2}{2} = 1$ The equality holds.

Inductive hypothesis: assume the equality holds for $n = k$ , i.e., $1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$

Inductive step: prove that the equality also holds for $n = k+1$ .

\begin{aligned} 1 + 2 + 3 + \cdots + k + (k+1) &= \frac{k(k+1)}{2} + (k+1) \quad \text{(using the inductive hypothesis)} \\ &= \frac{k(k+1) + 2(k+1)}{2} \\ &= \frac{(k+1)(k+2)}{2} \\ &= \frac{(k+1)[(k+1)+1]}{2} \end{aligned}

This is exactly the form of the formula for $n = k+1$ .

Conclusion: by mathematical induction, the equality holds for all positive integers $n$ .

Example 2: Proving a Power Inequality

Proposition: prove that $2^n > n$ for all positive integers $n$ .

Proof:

Base case: when $n = 1$ , $2^1 = 2 > 1$ , holds.

Inductive hypothesis: assume $2^k > k$ .

Inductive step:

\begin{aligned} 2^{k+1} &= 2 \cdot 2^k \\ &> 2k \quad \text{(using the inductive hypothesis)} \\ &> k + 1 \quad \text{(because when $k \geq 1$, $2k \geq k+1$)} \end{aligned}

Conclusion: by mathematical induction, $2^n > n$ for all positive integers $n$ .

Common Mistakes

Mistake 1: Forgetting the base case

Proving only the inductive step is not enough! For example, the proposition " $n = n+1$ " satisfies the inductive step (if $k = k+1$ , then $k+1 = k+2$ ), but it is clearly false.

Mistake 2: Not using the inductive hypothesis

The inductive step must use the inductive hypothesis. If proving $P(k+1)$ does not use $P(k)$ , then it is not induction.

Mistake 3: Circular reasoning

You cannot assume the conclusion you are trying to prove in order to prove the conclusion itself.

Practice Problems

Exercise 1

Use mathematical induction to prove: $1 + 3 + 5 + \cdots + (2n-1) = n^2$

Reference Answer(1 个标签)

mathematical induction

Proof:

Base case: when $n = 1$ , the left side $= 1$ and the right side $= 1^2 = 1$ , holds.

Inductive hypothesis: assume it holds for $n = k$ , i.e., $1 + 3 + 5 + \cdots + (2k-1) = k^2$

Inductive step:

\begin{aligned} &1 + 3 + 5 + \cdots + (2k-1) + (2(k+1)-1) \\ &= k^2 + (2k+1) \\ &= k^2 + 2k + 1 \\ &= (k+1)^2 \end{aligned}

Conclusion: by mathematical induction, the equality holds for all positive integers $n$ .

Exercise 2

Use mathematical induction to prove: $1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$

Reference Answer(1 个标签)

mathematical induction

Proof:

Base case: when $n = 1$ , the left side $= 1$ and the right side $= \frac{1 \times 2 \times 3}{6} = 1$ , holds.

Inductive hypothesis: assume it holds for $n = k$ .

Inductive step:

\begin{aligned} &1^2 + 2^2 + \cdots + k^2 + (k+1)^2 \\ &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \\ &= \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} \\ &= \frac{(k+1)[k(2k+1) + 6(k+1)]}{6} \\ &= \frac{(k+1)(2k^2 + 7k + 6)}{6} \\ &= \frac{(k+1)(k+2)(2k+3)}{6} \\ &= \frac{(k+1)[(k+1)+1][2(k+1)+1]}{6} \end{aligned}

Conclusion: by mathematical induction, the equality holds.

Exercise 3

Use mathematical induction to prove: $3^n > 2n + 1$ for all $n \geq 1$ .

Reference Answer(1 个标签)

mathematical induction

Proof:

Base case: when $n = 1$ , $3^1 = 3 > 2 \times 1 + 1 = 3$ … no, actually $3 \not> 3$ .

Let us start from $n = 2$ : $3^2 = 9 > 2 \times 2 + 1 = 5$ , holds.

Inductive hypothesis: assume $3^k > 2k + 1$ .

Inductive step:

\begin{aligned} 3^{k+1} &= 3 \cdot 3^k \\ &> 3(2k + 1) \quad \text{(inductive hypothesis)} \\ &= 6k + 3 \\ &> 2k + 3 \quad \text{(because when $k \geq 2$, $6k > 2k$)} \\ &= 2(k+1) + 1 \end{aligned}

Conclusion: by mathematical induction, the inequality holds for all $n \geq 2$ .

Summary

Symbols Used in This Article

符号	类型	读音/说明	在本文中的含义
$P(n)$	命题	P of n	A proposition about $n$
$n_0$	常数	n sub 0	The initial value
$k$	变量	k	The variable in the inductive hypothesis

中英对照

中文术语	英文术语	音标	说明
数学归纳法	mathematical induction	/ˌmæθəˈmætɪkəl ɪnˈdʌkʃən/	A method for proving propositions about natural numbers
基础步骤	base case	/beɪs keɪs/	Verifying the initial case
归纳假设	inductive hypothesis	/ɪnˈdʌktɪv haɪˈpɒθəsɪs/	Assuming the proposition holds for $n=k$
归纳步骤	inductive step	/ɪnˈdʌktɪv step/	Deriving from $n=k$ to $n=k+1$

Mathematical Induction

Proving Equalities