International Baccalaureate · DP 2: Analysis and Approaches HL

Proof by Mathematical Induction

⌚ ~67 min ▢ 8 blocks ✓ 38 exercises ➣ Prerequisites : Reasoning and Proof

I The Principle of Mathematical Induction

Proof by induction is a powerful technique used to prove that a proposition $P(n)$ is true for all integers $n$ above a certain starting value. It is analogous to knocking over a line of dominoes: if you can knock over the first one, and you know that each domino will knock over the next, then all dominoes will eventually fall.

Report an error

Method — The Principle of Mathematical Induction

To prove by induction that a proposition $P(n)$ is true for all integers $n \ge n_0$:

Base case (initialisation): check that $P(n_0)$ is true.
Inductive step (hérédité): assume $P(n)$ is true for an arbitrary integer $n \ge n_0$ (the induction hypothesis), and prove that $P(n+1)$ is then true.
Conclusion: by the principle of induction, $P(n)$ is true for all integers $n \ge n_0$.

Example

Prove by mathematical induction that for all integers $n \ge 1$, $$ 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}. $$

Answer

Let $P(n)$ be the proposition $$ P(n): \quad 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2} $$ for integers $n \ge 1$.

Base case $n=1$:
On the left-hand side, we have $1$. On the right-hand side, $$ \frac{1(1+1)}{2} = \frac{2}{2} = 1. $$ So $P(1)$ is true.
Inductive step:
Assume $P(n)$ is true for an arbitrary integer $n \ge 1$, that is, $$ 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}. $$ We must show that $P(n+1)$ is true: $$ 1 + 2 + 3 + \dots + n + (n+1) = \frac{(n+1)(n+2)}{2}. $$ Starting from the left-hand side of $P(n+1)$: $$ \begin{aligned} 1 + 2 + \dots + n + (n+1) &= \left(1 + 2 + \dots + n\right) + (n+1) \\ &= \frac{n(n+1)}{2} + (n+1) \quad &&\text{(by the induction hypothesis)}\\ &= \frac{n(n+1)}{2} + \frac{2(n+1)}{2} \\ &= \frac{(n+1)(n+2)}{2}. \end{aligned} $$ Thus $P(n+1)$ is true.
Conclusion:
Since $P(1)$ is true and $P(n) \Rightarrow P(n+1)$ for all integers $n \ge 1$, by the principle of mathematical induction, $P(n)$ is true for all integers $n \ge 1$.

Both Steps Are Needed

Neither step of an induction can be left out.

Without the inductive step, checking cases, however many, does not prove a statement for every $n$: $n^2 + n + 41$ takes the prime values $41$, $43$, $47$, $53$ for $n = 0, 1, 2, 3$, and a check value by value shows that it is prime for every $n$ from $0$ to $39$; yet for $n = 40$ it equals $40 \times 41 + 41 = 41^2$, which is not prime.
Without the base case, the inductive step does not prove the statement either. Let $P(n)$ be the proposition “$4^n + 1$ is divisible by $3$”. If $4^k + 1 = 3m$ for an integer $m$, then $$\begin{aligned}[t] 4^{k+1} + 1 &= 4\left(4^k + 1\right) - 3\\ &= 4 \times 3m - 3 && \text{(assumption $4^k + 1 = 3m$)}\\ &= 3(4m - 1), \end{aligned}$$ so $P(k) \Rightarrow P(k+1)$ holds for every $k$. But $P(1)$ is false, since $4^1 + 1 = 5$: no domino is pushed. The statement is not proved, and indeed $4^2 + 1 = 17$ and $4^3 + 1 = 65$ are not divisible by $3$ either.

Report an error

Example

Prove by mathematical induction that, for every integer $n \ge 1$, $$\sum_{r=1}^{n} r(2r-1) = \frac{n(n+1)(4n-1)}{6}.$$

Answer

Let $P(n)$ be the proposition $\displaystyle\sum_{r=1}^{n} r(2r-1) = \frac{n(n+1)(4n-1)}{6}$, for integers $n \ge 1$.

Base case $n = 1$: the left-hand side is $1 \times (2 - 1) = 1$ and the right-hand side is $\dfrac{1 \times 2 \times 3}{6} = 1$. So $P(1)$ is true.
Inductive step: assume $P(k)$ is true for some integer $k \ge 1$ (the inductive hypothesis). The sum up to $k + 1$ is the sum up to $k$ plus the term of rank $k + 1$: $$\begin{aligned}[t] \sum_{r=1}^{k+1} r(2r-1) &= \sum_{r=1}^{k} r(2r-1) + (k+1)(2k+1) && \text{(last term split off)}\\ &= \frac{k(k+1)(4k-1)}{6} + (k+1)(2k+1) && \text{(inductive hypothesis)}\\ &= \frac{(k+1)\left[k(4k-1) + 6(2k+1)\right]}{6} && \text{(factoring out $\tfrac{k+1}{6}$)}\\ &= \frac{(k+1)\left(4k^2 + 11k + 6\right)}{6}\\ &= \frac{(k+1)(k+2)(4k+3)}{6}. \end{aligned}$$ Since $k + 2 = (k+1) + 1$ and $4k + 3 = 4(k+1) - 1$, this is the formula at rank $k + 1$: $P(k+1)$ is true.
Conclusion: since $P(1)$ is true and $P(k) \Rightarrow P(k+1)$ for every integer $k \ge 1$, by the principle of mathematical induction, $P(n)$ is true for every integer $n \ge 1$.

Example

Prove by mathematical induction that $6^n + 4$ is divisible by $5$ for every natural number $n$.

Answer

Let $P(n)$ be the proposition “$6^n + 4$ is divisible by $5$”, for natural numbers $n$.

Base case $n = 0$: $6^0 + 4 = 5 = 5 \times 1$. So $P(0)$ is true.
Inductive step: assume $P(k)$ is true for some natural number $k$ (the inductive hypothesis). By the definition of divisibility, there is an integer $m$ such that $6^k + 4 = 5m$, that is $6^k = 5m - 4$. The power $6^{k+1}$ is written with $6^k$, which the hypothesis replaces: $$\begin{aligned}[t] 6^{k+1} + 4 &= 6 \times 6^k + 4\\ &= 6(5m - 4) + 4 && \text{(inductive hypothesis)}\\ &= 30m - 20\\ &= 5(6m - 4). \end{aligned}$$ Since $6m - 4$ is an integer, $6^{k+1} + 4$ is divisible by $5$: $P(k+1)$ is true.
Conclusion: since $P(0)$ is true and $P(k) \Rightarrow P(k+1)$ for every natural number $k$, by the principle of mathematical induction, $P(n)$ is true for every natural number $n$.

Skills to practice

Analyzing a Proof by Induction
Proving Sums by Induction
Proving Products by Induction
Proving Divisibility Properties by Induction

II Inequalities

Proposition — Bernoulli's Inequality

For every real number $a \ge 0$ and every integer $n \ge 0$,$$(1+a)^n \ge 1 + na.$$

Proof

We prove $P(n): (1+a)^n \ge 1+na$ by induction on $n$.

Base case. For $n=0$: $(1+a)^0 = 1$ and $1 + 0 \times a = 1$, so $P(0)$ is true.
Inductive step. Assume $(1+a)^n \ge 1+na$ for some $n \ge 0$. Since $1+a > 0$, multiplying both sides by $1+a$ preserves the inequality:$$\begin{aligned}[t] (1+a)^{n+1} &= (1+a)^n (1+a) \\ &\ge (1+na)(1+a) && {\scriptstyle(\text{induction hypothesis, } 1+a>0)} \\ &= 1 + (n+1)a + na^2 \\ &\ge 1 + (n+1)a && {\scriptstyle(na^2 \ge 0)}. \end{aligned}$$So $P(n+1)$ holds.
Conclusion. By induction, $(1+a)^n \ge 1+na$ for every $n \ge 0$.

Example

Prove by mathematical induction that $n! > 3^n$ for every integer $n \ge 7$.

Answer

Let $P(n)$ be the proposition “$n! > 3^n$”, for integers $n \ge 7$.

Base case $n = 7$: $7! = 5040$ and $3^7 = 2187$, and $5040 > 2187$. So $P(7)$ is true.
Inductive step: assume $P(k)$ is true for some integer $k \ge 7$, that is $k! > 3^k$ (the inductive hypothesis). Then $$\begin{aligned}[t] (k+1)! &= (k+1) \times k!\\ &> (k+1) \times 3^k && \text{(inductive hypothesis, $k + 1 > 0$)}\\ &\ge 3 \times 3^k && \text{($k + 1 \ge 3$, since $k \ge 7$)}\\ &= 3^{k+1}. \end{aligned}$$ So $P(k+1)$ is true.
Conclusion: since $P(7)$ is true and $P(k) \Rightarrow P(k+1)$ for every integer $k \ge 7$, by the principle of mathematical induction, $n! > 3^n$ for every integer $n \ge 7$.

The starting value matters: $6! = 720 < 729 = 3^6$, so the inequality $6! > 3^6$ is false. The inductive step works for every $k \ge 2$, but the first domino that falls is $n = 7$.

Skills to practice

Proving Inequalities by Induction

III Recursive Sequences

Definition — Increasing and Decreasing Sequences

Let $(u_n)$ be a sequence.

The sequence $(u_n)$ is increasing from index $n_0$ if for all $n \ge n_0$, $\boldsymbol{u_{n+1} \ge u_n}$.
The sequence $(u_n)$ is decreasing from index $n_0$ if for all $n \ge n_0$, $\boldsymbol{u_{n+1} \le u_n}$.
A sequence that is either increasing or decreasing is said to be monotonic.

Definition — Upper and Lower Bounds

Let $(u_n)$ be a sequence.

$(u_n)$ is upper bounded if there exists a real $M$ such that for all $n$, $\boldsymbol{u_n \le M}$. $M$ is an upper bound.
$(u_n)$ is lower bounded if there exists a real $m$ such that for all $n$, $\boldsymbol{u_n \ge m}$. $m$ is a lower bound.
$(u_n)$ is bounded if it is both upper and lower bounded.

Example — An Induction on a Recursive Sequence

The sequence $(u_n)$ is defined by $u_0 = 1$ and, for every natural number $n$, $u_{n+1} = \dfrac{1}{2}u_n + 2$.

Prove by induction that $u_n \le 4$ for every natural number $n$.
Deduce that the sequence $(u_n)$ is increasing.
Prove by induction that $u_n = 4 - \dfrac{3}{2^n}$ for every natural number $n$.

Answer

Let $P(n)$ be the proposition “$u_n \le 4$”, for natural numbers $n$. Base case: $u_0 = 1 \le 4$, so $P(0)$ is true. Inductive step: assume $u_k \le 4$ for some natural number $k$ (the inductive hypothesis). Multiplying by $\frac{1}{2} > 0$ keeps the direction of the inequality: $$\begin{aligned}[t] u_{k+1} &= \frac{1}{2}u_k + 2\\ &\le \frac{1}{2} \times 4 + 2 && \text{(inductive hypothesis)}\\ &= 4. \end{aligned}$$ So $P(k+1)$ is true. Conclusion: since $P(0)$ is true and $P(k) \Rightarrow P(k+1)$ for every natural number $k$, by the principle of mathematical induction, $u_n \le 4$ for every natural number $n$.
For every natural number $n$, $$\begin{aligned}[t] u_{n+1} - u_n &= \frac{1}{2}u_n + 2 - u_n\\ &= \frac{1}{2}\left(4 - u_n\right)\\ &\ge 0 && \text{(part 1: $u_n \le 4$)}. \end{aligned}$$ So $u_{n+1} \ge u_n$ for every $n$: the sequence $(u_n)$ is increasing.
Let $Q(n)$ be the proposition $u_n = 4 - \dfrac{3}{2^n}$, for natural numbers $n$. Base case: $4 - \dfrac{3}{2^0} = 4 - 3 = 1 = u_0$, so $Q(0)$ is true. Inductive step: assume $u_k = 4 - \dfrac{3}{2^k}$ for some natural number $k$ (the inductive hypothesis). Then $$\begin{aligned}[t] u_{k+1} &= \frac{1}{2}u_k + 2\\ &= \frac{1}{2}\left(4 - \frac{3}{2^k}\right) + 2 && \text{(inductive hypothesis)}\\ &= 2 - \frac{3}{2^{k+1}} + 2\\ &= 4 - \frac{3}{2^{k+1}}. \end{aligned}$$ So $Q(k+1)$ is true. Conclusion: by the principle of mathematical induction, $u_n = 4 - \dfrac{3}{2^n}$ for every natural number $n$. This formula confirms parts 1 and 2: $\dfrac{3}{2^n} > 0$, and it decreases as $n$ increases.

Skills to practice

Proving an Explicit Formula for a Sequence
Proving Properties of a Sequence

IV Going further

Skills to practice

Solving Problems by Induction