Proof by Mathematical Induction

Some statements claim to be true for every positive integer $n$: a formula for a sum, a divisibility rule, a pattern in derivatives. You can’t check infinitely many cases one by one, and checking a few proves nothing. Mathematical induction gets around this: you prove the first case, then prove that each case guarantees the next. Like a line of dominoes, once the first one falls, they all fall.

Key ideas

The idea: dominoes

Imagine an endless line of dominoes. To be sure every one of them falls, you need two facts:

1. The first domino falls.
2. Whenever one domino falls, it knocks over the next one.

Induction works the same way. Let $P(n)$ be the statement you want to prove, for example "$1 + 3 + 5 + \dots + (2n - 1) = n^2$". If $P(1)$ is true, and $P(k)$ being true always makes $P(k + 1)$ true, then $P(1)$ gives $P(2)$, which gives $P(3)$, and so on forever.

The four parts of a proof

Every induction proof has the same structure. Examiners look for all four parts.

1. Base case. Show that $P(1)$ is true. (If the statement starts at a different value, such as $n \ge 0$ or $n \ge 2$, start there.)
2. Assumption. Assume that $P(k)$ is true for some positive integer $k$. Write out exactly what this says.
3. Inductive step. Using the assumption, prove that $P(k + 1)$ is true. It helps to write down what $P(k + 1)$ says first, so you know your target.
4. Conclusion. Write a sentence like this one:

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}^+$.

Proofs about sums

For a formula like $\displaystyle\sum_{r=1}^{n} u_r = f(n)$, the key fact is that the sum up to $k + 1$ is the sum up to $k$ plus one more term:

$$\sum_{r=1}^{k+1} u_r = \sum_{r=1}^{k} u_r + u_{k+1} = f(k) + u_{k+1}$$

Use the assumption to replace the first part with $f(k)$, then simplify until you reach $f(k + 1)$. Factoring out a common factor early (rather than expanding everything) usually makes the algebra much shorter.

Proofs about divisibility

To prove that an expression is divisible by a number $d$, the assumption becomes ”$f(k) = dm$ for some integer $m$”. In the inductive step, rewrite $f(k + 1)$ so that it contains $f(k)$, replace $f(k)$ with $dm$, and factor out $d$. Exponents like $6^{k+1}$ are rewritten as $6 \times 6^k$.

Other places induction appears

The IB guide links induction to sums of sequences, divisibility, differentiation and complex numbers.

• Repeated derivatives. To prove a formula for the $n$th derivative $f^{(n)}(x)$ or $\dfrac{d^ny}{dx^n}$, assume the formula for the $k$th derivative and differentiate it once more to get the $(k + 1)$th. Example 4 does this. Notation for higher derivatives is on higher-order derivatives.
• Complex numbers. De Moivre’s theorem, $(\cos\theta + i\sin\theta)^n = \cos n\theta + i\sin n\theta$, is proved by induction for positive integers $n$. See De Moivre’s theorem.

Worked examples

Example 1: The sum of the odd numbers

Prove by induction that, for all $n \in \mathbb{Z}^+$,

$$1 + 3 + 5 + \dots + (2n - 1) = n^2$$

Solution. Let $P(n)$ be the statement $\displaystyle\sum_{r=1}^{n} (2r - 1) = n^2$.

Base case. When $n = 1$: LHS $= 2(1) - 1 = 1$ and RHS $= 1^2 = 1$. So $P(1)$ is true.

Assumption. Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$:

$$1 + 3 + 5 + \dots + (2k - 1) = k^2$$

Inductive step. We want to show $P(k + 1)$: $1 + 3 + \dots + (2k - 1) + (2k + 1) = (k + 1)^2$. The new term is $2(k + 1) - 1 = 2k + 1$.

$$\begin{aligned} 1 + 3 + \dots + (2k - 1) + (2k + 1) &= k^2 + (2k + 1) && \text{by the assumption} \\ &= (k + 1)^2 \end{aligned}$$

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}^+$.

Example 2: A sum with a cubic formula

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}^+$.

Solution. Let $P(n)$ be the statement above.

Base case. When $n = 1$: LHS $= 1(2) = 2$ and RHS $= \dfrac{1(2)(3)}{3} = 2$. So $P(1)$ is true.

Assumption. Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$:

$$\sum_{r=1}^{k} r(r + 1) = \frac{k(k + 1)(k + 2)}{3}$$

Inductive step. Target: $\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) && \text{by the assumption} \\ &= \frac{k(k + 1)(k + 2) + 3(k + 1)(k + 2)}{3} \\ &= \frac{(k + 1)(k + 2)(k + 3)}{3} && \text{factor out } (k + 1)(k + 2) \end{aligned}$$

This is the RHS of $P(k + 1)$, 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}^+$.

Notice the factoring step: taking out $(k + 1)(k + 2)$ straight away avoids expanding a cubic.

Example 3: Divisibility

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

Solution. Let $P(n)$ be the statement ”$3^{2n} + 7$ is divisible by $8$”.

Base case. When $n = 1$: $3^2 + 7 = 16 = 8 \times 2$. So $P(1)$ is true.

Assumption. Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$. Then $3^{2k} + 7 = 8m$ for some integer $m$, so

$$3^{2k} = 8m - 7$$

Inductive step. Target: $3^{2(k+1)} + 7$ is divisible by $8$.

$$\begin{aligned} 3^{2(k+1)} + 7 &= 3^{2k} \times 3^2 + 7 \\ &= 9(8m - 7) + 7 && \text{by the assumption} \\ &= 72m - 63 + 7 \\ &= 72m - 56 \\ &= 8(9m - 7) \end{aligned}$$

Since $9m - 7$ is an integer, $3^{2(k+1)} + 7$ is divisible by $8$. 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 $3^{2n} + 7$ is divisible by $8$ for all $n \in \mathbb{Z}^+$.

Example 4: The nth derivative

Let $f(x) = xe^{2x}$. Prove by induction that, for all $n \in \mathbb{Z}^+$,

$$f^{(n)}(x) = 2^{n-1}(2x + n)e^{2x}$$

Solution. Let $P(n)$ be the statement above.

Base case. By the product rule,

$$f'(x) = 1 \cdot e^{2x} + x \cdot 2e^{2x} = (2x + 1)e^{2x}$$

and the formula gives $2^0(2x + 1)e^{2x} = (2x + 1)e^{2x}$. So $P(1)$ is true.

Assumption. Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$:

$$f^{(k)}(x) = 2^{k-1}(2x + k)e^{2x}$$

Inductive step. Target: $f^{(k+1)}(x) = 2^{k}(2x + k + 1)e^{2x}$. The $(k + 1)$th derivative is the derivative of the $k$th derivative, so differentiate the assumption with the product rule:

$$\begin{aligned} f^{(k+1)}(x) &= \frac{d}{dx}\Big(2^{k-1}(2x + k)e^{2x}\Big) \\ &= 2^{k-1}\Big(2e^{2x} + (2x + k) \cdot 2e^{2x}\Big) \\ &= 2^{k-1} \cdot 2\,(1 + 2x + k)e^{2x} \\ &= 2^{k}(2x + k + 1)e^{2x} \end{aligned}$$

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}^+$.

Common mistakes

Checking a few cases and stopping. Showing the formula works for $n = 1, 2, 3$ is not a proof. You need the inductive step: a general argument that works for every $k$.

Assuming what you’re trying to prove. You may assume $P(k)$. You may not assume $P(k + 1)$; that’s the thing you’re proving. Start from one side of $P(k + 1)$ (usually the sum, or the expression) and work towards the other.

Not using the assumption. If your inductive step never uses $P(k)$, something is wrong. Point out where you use it (“by the assumption”).

Getting the new term wrong. In a sum, the extra term is $u_{k+1}$: replace $r$ with $k + 1$ in the general term. For $\displaystyle\sum (2r - 1)$ it’s $2(k + 1) - 1 = 2k + 1$, not $2k - 1$.

Expanding everything. In sum proofs, expanding both sides into big polynomials is slow and error-prone. Look for a common factor, like $(k + 1)$, and take it out first.

Leaving out the conclusion, or writing it vaguely. The final sentence is part of the proof and earns marks. Say that $P(1)$ is true, that $P(k)$ implies $P(k + 1)$, and therefore $P(n)$ is true for all $n \in \mathbb{Z}^+$.

Practice

1. (Warm-up) Let $P(n)$ be the statement $1 + 2 + 3 + \dots + n = \dfrac{n(n + 1)}{2}$.

• (a) Show that $P(1)$ is true.
• (b) Write down the statements $P(k)$ and $P(k + 1)$.

Solution

(a) When $n = 1$: LHS $= 1$ and RHS $= \dfrac{1(2)}{2} = 1$. So $P(1)$ is true.

(b) $P(k)$: $1 + 2 + \dots + k = \dfrac{k(k + 1)}{2}$.

$P(k + 1)$: $1 + 2 + \dots + k + (k + 1) = \dfrac{(k + 1)(k + 2)}{2}$.

2. (Warm-up) Complete the proof from Question 1: prove by induction that $\displaystyle\sum_{r=1}^{n} r = \frac{n(n + 1)}{2}$ for all $n \in \mathbb{Z}^+$.

Solution

Base case. Shown in Question 1: $P(1)$ is true.

Assumption. Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$: $\displaystyle\sum_{r=1}^{k} r = \frac{k(k + 1)}{2}$.

Inductive step.

$$\begin{aligned} \sum_{r=1}^{k+1} r &= \frac{k(k + 1)}{2} + (k + 1) && \text{by the assumption} \\ &= \frac{k(k + 1) + 2(k + 1)}{2} \\ &= \frac{(k + 1)(k + 2)}{2} \end{aligned}$$

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}^+$.

3. (Warm-up) Prove by induction that $1 + 2 + 4 + \dots + 2^{n-1} = 2^n - 1$ for all $n \in \mathbb{Z}^+$.

Solution

Let $P(n)$ be the statement $\displaystyle\sum_{r=1}^{n} 2^{r-1} = 2^n - 1$.

Base case. When $n = 1$: LHS $= 2^0 = 1$ and RHS $= 2^1 - 1 = 1$. So $P(1)$ is true.

Assumption. Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$: $\displaystyle\sum_{r=1}^{k} 2^{r-1} = 2^k - 1$.

Inductive step. The new term is $2^{(k+1) - 1} = 2^k$:

$$\begin{aligned} \sum_{r=1}^{k+1} 2^{r-1} &= (2^k - 1) + 2^k && \text{by the assumption} \\ &= 2 \times 2^k - 1 \\ &= 2^{k+1} - 1 \end{aligned}$$

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}^+$.

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

Solution

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

Base case. When $n = 1$: LHS $= 1$ and RHS $= \dfrac{1(2)(3)}{6} = 1$. So $P(1)$ is true.

Assumption. Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$: $\displaystyle\sum_{r=1}^{k} r^2 = \frac{k(k + 1)(2k + 1)}{6}$.

Inductive step. Target: $\displaystyle\sum_{r=1}^{k+1} r^2 = \frac{(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 && \text{by the assumption} \\ &= \frac{(k + 1)\big(k(2k + 1) + 6(k + 1)\big)}{6} && \text{factor out } (k + 1) \\ &= \frac{(k + 1)(2k^2 + 7k + 6)}{6} \\ &= \frac{(k + 1)(k + 2)(2k + 3)}{6} \end{aligned}$$

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}^+$.

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

Solution

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

Base case. When $n = 1$: LHS $= \dfrac{1}{1 \times 2} = \dfrac{1}{2}$ and RHS $= \dfrac{1}{2}$. So $P(1)$ is true.

Assumption. Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$: $\displaystyle\sum_{r=1}^{k} \frac{1}{r(r + 1)} = \frac{k}{k + 1}$.

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

$$\begin{aligned} \sum_{r=1}^{k+1} \frac{1}{r(r + 1)} &= \frac{k}{k + 1} + \frac{1}{(k + 1)(k + 2)} && \text{by the assumption} \\ &= \frac{k(k + 2) + 1}{(k + 1)(k + 2)} \\ &= \frac{k^2 + 2k + 1}{(k + 1)(k + 2)} \\ &= \frac{(k + 1)^2}{(k + 1)(k + 2)} \\ &= \frac{k + 1}{k + 2} \end{aligned}$$

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}^+$.

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

Solution

Let $P(n)$ be the statement ”$7^n - 1$ is divisible by $6$”.

Base case. When $n = 1$: $7 - 1 = 6 = 6 \times 1$. So $P(1)$ is true.

Assumption. Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$: $7^k - 1 = 6m$ for some integer $m$, so $7^k = 6m + 1$.

Inductive step.

$$\begin{aligned} 7^{k+1} - 1 &= 7 \times 7^k - 1 \\ &= 7(6m + 1) - 1 && \text{by the assumption} \\ &= 42m + 6 \\ &= 6(7m + 1) \end{aligned}$$

Since $7m + 1$ is an integer, $7^{k+1} - 1$ is divisible by $6$, 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 $7^n - 1$ is divisible by $6$ for all $n \in \mathbb{Z}^+$.

7. (Core) Prove by induction that $\dfrac{d^n}{dx^n}\left(xe^x\right) = (x + n)e^x$ for all $n \in \mathbb{Z}^+$.

Solution

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

Base case. By the product rule, $\dfrac{d}{dx}\left(xe^x\right) = e^x + xe^x = (x + 1)e^x$, which matches the formula with $n = 1$. So $P(1)$ is true.

Assumption. Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$: $\dfrac{d^k}{dx^k}\left(xe^x\right) = (x + k)e^x$.

Inductive step. Differentiate both sides of the assumption once more:

$$\begin{aligned} \frac{d^{k+1}}{dx^{k+1}}\left(xe^x\right) &= \frac{d}{dx}\Big((x + k)e^x\Big) \\ &= 1 \cdot e^x + (x + k)e^x \\ &= (x + k + 1)e^x \end{aligned}$$

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}^+$.

8. (Challenge) Prove by induction that $5^n + 2 \times 11^n$ is divisible by $3$ for all $n \in \mathbb{Z}^+$.

Solution

Let $P(n)$ be the statement ”$5^n + 2 \times 11^n$ is divisible by $3$”.

Base case. When $n = 1$: $5 + 22 = 27 = 3 \times 9$. So $P(1)$ is true.

Assumption. Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$: $5^k + 2 \times 11^k = 3m$ for some integer $m$.

Inductive step. Split the $11$ as $5 + 6$ so the expression from $P(k)$ appears:

$$\begin{aligned} 5^{k+1} + 2 \times 11^{k+1} &= 5 \times 5^k + 11 \times 2 \times 11^k \\ &= 5 \times 5^k + 5 \times 2 \times 11^k + 6 \times 2 \times 11^k \\ &= 5\left(5^k + 2 \times 11^k\right) + 12 \times 11^k \\ &= 5(3m) + 12 \times 11^k && \text{by the assumption} \\ &= 3\left(5m + 4 \times 11^k\right) \end{aligned}$$

Since $5m + 4 \times 11^k$ is an integer, $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 $5^n + 2 \times 11^n$ is divisible by $3$ for all $n \in \mathbb{Z}^+$.

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

Solution

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

Base case. When $n = 1$: LHS $= 1 \times 1! = 1$ and RHS $= 2! - 1 = 1$. So $P(1)$ is true.

Assumption. Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$: $\displaystyle\sum_{r=1}^{k} r \times r! = (k + 1)! - 1$.

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

$$\begin{aligned} \sum_{r=1}^{k+1} r \times r! &= (k + 1)! - 1 + (k + 1) \times (k + 1)! && \text{by the assumption} \\ &= (k + 1)!\,\big(1 + (k + 1)\big) - 1 \\ &= (k + 2) \times (k + 1)! - 1 \\ &= (k + 2)! - 1 \end{aligned}$$

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}^+$.