6.4 Proof by Mathematical Induction

AHL 1.15

In this section you will learn
  • the idea behind mathematical induction
  • the four parts of an induction proof, and how to write the concluding statement
  • how to prove results about sums (series), recurrence relations, divisibility and inequalities

The idea: falling dominoes

Imagine an endless line of dominoes, standing close together. Suppose we know two things:

  1. the first domino falls, and
  2. whenever any domino falls, it knocks over the next one.

Then every domino falls: the 1st knocks over the 2nd, the 2nd knocks over the 3rd, and so on, for ever.

Mathematical induction uses exactly this idea for statements \(P(n)\) about positive integers \(n\).

Principle of mathematical induction Not in the formula booklet

If

  • \(P(1)\) is true, and
  • for every \(k \in \mathbb{Z}^+\), if \(P(k)\) is true then \(P(k + 1)\) is true,

then \(P(n)\) is true for all \(n \in \mathbb{Z}^+\).

  • \(P(n)\): a statement about the positive integer \(n\) (for example a formula to be proved)
  • \(k\): one positive integer (any value), used in the inductive step
  • \(n\): any positive integer

Checking many values of \(n\) is not a proof — there are infinitely many. Induction proves all of them at once.

How to set out an induction proof

The four parts

  1. Statement. Write \(P(n)\): the statement to be proved.
  2. Basis. Show that \(P(1)\) is true (or \(P(n_0)\) for the first value).
  3. Inductive step. Assume \(P(k)\) is true for some \(k \in \mathbb{Z}^+\). Using this assumption, prove that \(P(k + 1)\) is true. Write down what \(P(k + 1)\) says before you start, so you know your target.
  4. Conclusion. “Since \(P(1)\) is true, and \(P(k)\) true implies \(P(k + 1)\) true, by the principle of mathematical induction \(P(n)\) is true for all \(n \in \mathbb{Z}^+\).”

In IB examinations, marks are given for each part, including the final conclusion. Do not leave any out.

Sums

For a sum, the key step is: the sum to \(k + 1\) terms = the sum to \(k\) terms + the \((k + 1)\)th term.

Example 1 Prove by induction that \(\displaystyle\sum_{r=1}^{n} r(r + 1) = \frac{n(n + 1)(n + 2)}{3}\) for all \(n \in \mathbb{Z}^+\).

Let \(P(n)\) be the statement \(\displaystyle\sum_{r=1}^{n} r(r + 1) = \frac{n(n + 1)(n + 2)}{3}\).

Basis. \(n = 1\): LHS \(= 1 \times 2 = 2\). RHS \(= \dfrac{1 \times 2 \times 3}{3} = 2\). So \(P(1)\) is true.

Inductive step. Assume \(P(k)\) is true: \(\displaystyle\sum_{r=1}^{k} r(r + 1) = \frac{k(k + 1)(k + 2)}{3}\).

We want to prove \(P(k + 1)\): \(\displaystyle\sum_{r=1}^{k+1} r(r + 1) = \frac{(k + 1)(k + 2)(k + 3)}{3}\).

\[ \begin{aligned} \sum_{r=1}^{k+1} r(r + 1) &= \sum_{r=1}^{k} r(r + 1) + (k + 1)(k + 2) \\ &= \frac{k(k + 1)(k + 2)}{3} + (k + 1)(k + 2) && {\color{#9F353A}\text{by the assumption}} \\ &= \frac{(k + 1)(k + 2)\,(k + 3)}{3} && {\color{#9F353A}\text{common factor}} . \end{aligned} \]

(In the last step, take out the common factor \((k + 1)(k + 2)\): \(\frac{k}{3} + 1 = \frac{k + 3}{3}\).) So \(P(k + 1)\) is true.

Conclusion. Since \(P(1)\) is true, and \(P(k)\) true implies \(P(k + 1)\) true, by the principle of mathematical induction \(P(n)\) is true for all \(n \in \mathbb{Z}^+\).

Tip: do not expand everything. Look for the common factor — it is usually part of the target.

Example 2 Prove by induction that \(\dfrac{1}{1 \times 3} + \dfrac{1}{3 \times 5} + \cdots + \dfrac{1}{(2n - 1)(2n + 1)} = \dfrac{n}{2n + 1}\) for all \(n \in \mathbb{Z}^+\).

Let \(P(n)\) be the statement above.

Basis. \(n = 1\): LHS \(= \dfrac{1}{3}\), RHS \(= \dfrac{1}{3}\). True.

Inductive step. Assume \(P(k)\): the sum to \(k\) terms is \(\dfrac{k}{2k + 1}\). Target \(P(k + 1)\): the sum is \(\dfrac{k + 1}{2k + 3}\).

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

So \(P(k + 1)\) is true.

Conclusion. Since \(P(1)\) is true, and \(P(k)\) true implies \(P(k + 1)\) true, \(P(n)\) is true for all \(n \in \mathbb{Z}^+\) by induction.

Example 3 (a) Prove by induction that \(\displaystyle\sum_{r=1}^{n} r^2 = \frac{n(n + 1)(2n + 1)}{6}\) for all \(n \in \mathbb{Z}^+\).

(b) Hence show that \(\displaystyle\sum_{r=n+1}^{2n} r^2 = \frac{n(2n + 1)(7n + 1)}{6}\).

(a) Basis. \(n = 1\): LHS \(= 1\), RHS \(= \dfrac{1 \times 2 \times 3}{6} = 1\). True.

Inductive step. Assume \(\displaystyle\sum_{r=1}^{k} r^2 = \frac{k(k + 1)(2k + 1)}{6}\). Target: \(\dfrac{(k + 1)(k + 2)(2k + 3)}{6}\).

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

Conclusion. By induction, the result is true for all \(n \in \mathbb{Z}^+\).

(b) Subtract the first \(n\) terms from the first \(2n\) terms:

\[ \begin{aligned} \sum_{r=n+1}^{2n} r^2 &= \frac{2n(2n + 1)(4n + 1)}{6} - \frac{n(n + 1)(2n + 1)}{6} = \frac{n(2n + 1)\big[2(4n + 1) - (n + 1)\big]}{6} \\ &= \frac{n(2n + 1)(7n + 1)}{6} . \end{aligned} \]

Example 4 Prove by induction that \(\displaystyle\sum_{r=1}^{n} r \times r! = (n + 1)! - 1\) for all \(n \in \mathbb{Z}^+\).

Basis. \(n = 1\): LHS \(= 1 \times 1! = 1\), RHS \(= 2! - 1 = 1\). True.

Inductive step. Assume \(\displaystyle\sum_{r=1}^{k} r \times r! = (k + 1)! - 1\). Target: \((k + 2)! - 1\).

\[ \sum_{r=1}^{k+1} r \times r! = (k + 1)! - 1 + (k + 1)(k + 1)! = (k + 1)!\,(1 + k + 1) - 1 = (k + 2)! - 1 . \]

(We used \((k + 2) \times (k + 1)! = (k + 2)!\).)

Conclusion. By induction, the result is true for all \(n \in \mathbb{Z}^+\).

Recurrence relations

Example 5 A sequence is defined by \(u_1 = 1\) and \(u_{n+1} = 2u_n + 1\). Prove by induction that \(u_n = 2^n - 1\) for all \(n \in \mathbb{Z}^+\).

Basis. \(u_1 = 1\) and \(2^1 - 1 = 1\). True.

Inductive step. Assume \(u_k = 2^k - 1\). Then

\[ u_{k+1} = 2u_k + 1 = 2\left(2^k - 1\right) + 1 = 2^{k+1} - 1, \]

which is the formula with \(n = k + 1\).

Conclusion. By induction, \(u_n = 2^n - 1\) for all \(n \in \mathbb{Z}^+\).

Divisibility

“\(f(n)\) is divisible by \(d\)” means \(f(n) = d \times (\text{an integer})\). In the inductive step, write \(f(k + 1)\) in terms of \(f(k)\), and replace \(f(k)\) by \(dM\).

Example 6 Prove by induction that \(7^n - 1\) is divisible by 6 for all \(n \in \mathbb{Z}^+\).

Basis. \(n = 1\): \(7 - 1 = 6\), which is divisible by 6.

Inductive step. Assume \(7^k - 1 = 6M\) for some \(M \in \mathbb{Z}\), so \(7^k = 6M + 1\). Then

\[ 7^{k+1} - 1 = 7 \times 7^k - 1 = 7(6M + 1) - 1 = 42M + 6 = 6(7M + 1), \]

which is divisible by 6, since \(7M + 1 \in \mathbb{Z}\).

Conclusion. By induction, \(7^n - 1\) is divisible by 6 for all \(n \in \mathbb{Z}^+\).

Inequalities

The first value does not have to be \(n = 1\). The basis is then the first value for which the statement is claimed.

Example 7 Prove by induction that \(2^n > n^2\) for all integers \(n \ge 5\).

Basis. \(n = 5\): \(2^5 = 32 > 25 = 5^2\). True.

Inductive step. Assume \(2^k > k^2\) for some integer \(k \ge 5\). Then

\[ 2^{k+1} = 2 \times 2^k > 2k^2 . \]

We need \(2k^2 \ge (k + 1)^2\), that is \(k^2 - 2k - 1 \ge 0\), or \((k - 1)^2 \ge 2\). This is true for \(k \ge 5\) (since \((k - 1)^2 \ge 16\)). So

\[ 2^{k+1} > 2k^2 \ge (k + 1)^2 . \]

Conclusion. Since the statement is true for \(n = 5\), and true for \(k\) implies true for \(k + 1\) (for \(k \ge 5\)), by induction \(2^n > n^2\) for all integers \(n \ge 5\).

Common errors

✗ Wrong ✓ Right Why
Assuming \(P(n)\) is true for all \(n\) Assume \(P(k)\) for some \(k\) Otherwise you assume what you want to prove.
Missing the conclusion Write the full concluding sentence It carries marks in the IB.
Not using the assumption Substitute \(P(k)\) into the working The inductive step must use it.
Adding the wrong last term Term \(k + 1\) is \(u_{k+1}\) e.g. \((k + 1)(k + 2)\), not \(k(k + 1)\).
Basis \(n = 1\) for “\(n \ge 5\)” Start at \(n = 5\) The basis is the first value claimed.

Exercises

In each question, give a full proof by induction.

1 Prove that \(1 + 3 + 5 + \cdots + (2n - 1) = n^2\) for all \(n \in \mathbb{Z}^+\).

Basis: \(1 = 1^2\). Step: assume the sum to \(k\) terms is \(k^2\). Then the sum to \(k + 1\) terms is \(k^2 + (2k + 1) = (k + 1)^2\). Conclusion as in the examples.

2 Prove that \(\displaystyle\sum_{r=1}^{n} r = \frac{n(n + 1)}{2}\) for all \(n \in \mathbb{Z}^+\).

Basis: \(1 = \frac{1 \times 2}{2}\). Step: \(\dfrac{k(k + 1)}{2} + (k + 1) = \dfrac{(k + 1)(k + 2)}{2}\). Conclusion.

3 Prove that \(1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1\) for all \(n \in \mathbb{Z}^+\).

Basis: \(1 = 2 - 1\). Step: \((2^k - 1) + 2^k = 2^{k+1} - 1\). Conclusion.

4 Prove that \(\displaystyle\sum_{r=1}^{n} r^3 = \frac{n^2(n + 1)^2}{4}\) for all \(n \in \mathbb{Z}^+\).

Basis: \(1 = \frac{1 \times 4}{4}\). Step:

\[ \frac{k^2(k + 1)^2}{4} + (k + 1)^3 = \frac{(k + 1)^2\left(k^2 + 4k + 4\right)}{4} = \frac{(k + 1)^2(k + 2)^2}{4} . \]

Conclusion.

5 Prove that \(\displaystyle\sum_{r=1}^{n} \frac{1}{(r + 1)(r + 2)} = \frac{n}{2(n + 2)}\) for all \(n \in \mathbb{Z}^+\).

Basis: \(\frac{1}{6} = \frac{1}{2 \times 3}\). Step:

\[ \frac{k}{2(k + 2)} + \frac{1}{(k + 2)(k + 3)} = \frac{k(k + 3) + 2}{2(k + 2)(k + 3)} = \frac{(k + 1)(k + 2)}{2(k + 2)(k + 3)} = \frac{k + 1}{2(k + 3)} . \]

Conclusion.

6 Prove that \(5^n - 1\) is divisible by 4 for all \(n \in \mathbb{Z}^+\).

Basis: \(4\). Step: assume \(5^k = 4M + 1\). Then \(5^{k+1} - 1 = 5(4M + 1) - 1 = 4(5M + 1)\). Conclusion.

7 Prove that \(n^3 + 2n\) is divisible by 3 for all \(n \in \mathbb{Z}^+\).

Basis: \(1 + 2 = 3\). Step: assume \(k^3 + 2k = 3M\). Then

\[ (k + 1)^3 + 2(k + 1) = k^3 + 3k^2 + 5k + 3 = (k^3 + 2k) + 3(k^2 + k + 1) = 3\left(M + k^2 + k + 1\right). \]

Conclusion.

8 A sequence is defined by \(u_1 = 3\) and \(u_{n+1} = 3u_n - 2\). Prove that \(u_n = 2 \times 3^{\,n-1} + 1\).

Basis: \(2 \times 1 + 1 = 3\). Step: \(u_{k+1} = 3\left(2 \times 3^{k-1} + 1\right) - 2 = 2 \times 3^{k} + 1\). Conclusion.

9 Prove that \(3^n > 2n + 1\) for all integers \(n \ge 2\).

Basis: \(9 > 5\). Step: assume \(3^k > 2k + 1\) (\(k \ge 2\)). Then \(3^{k+1} > 3(2k + 1) = 6k + 3 > 2k + 3 = 2(k + 1) + 1\), since \(4k > 0\). Conclusion (for \(n \ge 2\)).

10 Prove that \((1 + x)^n \ge 1 + nx\) for all \(n \in \mathbb{Z}^+\) and all \(x > -1\).

Basis: \(1 + x \ge 1 + x\). Step: assume \((1 + x)^k \ge 1 + kx\). Since \(1 + x > 0\), multiplying keeps the inequality:

\[ (1 + x)^{k+1} \ge (1 + kx)(1 + x) = 1 + (k + 1)x + kx^2 \ge 1 + (k + 1)x, \]

because \(kx^2 \ge 0\). Conclusion.