Proof by induction: identities and divisibility
Picture a long line of dominoes outside a GAA clubhouse for a charity event. You cannot push every domino by hand, but you can be sure they all fall if two things hold: the first one falls, and each domino knocks over the next. Proof by induction works in exactly the same way. How can we be sure that $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$ for every $n$, when we can only ever check a few values?
The idea of induction
Let $P(n)$ be a statement that depends on a natural number $n$. For example, $P(n)$: $1 + 2 + \dots + n = \frac{n(n+1)}{2}$.
Checking $n = 1, 2, 3, \dots$ one at a time never finishes. Induction replaces infinitely many checks with two.
Why does this work? $P(1)$ is true by Step 1. Step 2 then gives $P(2)$, which gives $P(3)$, and so on, like dominoes falling one after another.
Proving sum formulae
The key move is in the inductive step. You assume $P(k)$, then write the sum up to $k+1$ as "the sum up to $k$" plus one more term, and replace the first part using the assumption.
A good habit is to write down $P(k+1)$ before you start, so you know exactly what you are aiming for.
Let $P(n)$ be the statement $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$. a) Verify that $P(1)$ is true. b) Write down $P(k)$ and $P(k+1)$. c) Assuming $P(k)$ is true,…
Let $P(n)$ be the statement $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$.
- a) Verify that $P(1)$ is true.
- b) Write down $P(k)$ and $P(k+1)$.
- c) Assuming $P(k)$ is true, show that $P(k+1)$ is true.
Let $P(n)$ be the statement $1 + 3 + 5 + \dots + (2n-1) = n^2$. a) Show that $P(1)$ and $P(2)$ are true. b) Assuming $P(k)$ is true for some $k \in \mathbb{N}$, prove…
Let $P(n)$ be the statement $1 + 3 + 5 + \dots + (2n-1) = n^2$.
- a) Show that $P(1)$ and $P(2)$ are true.
- b) Assuming $P(k)$ is true for some $k \in \mathbb{N}$, prove that $P(k+1)$ is true.
The same method proves the sum of a finite geometric series, $1 + r + \dots + r^{n-1} = \frac{r^n - 1}{r - 1}$. The new term added at the inductive step is $r^k$. Fractions such as $\frac{1}{n(n+1)}$ work the same way: add the next term, then combine over a common denominator.
Prove by induction that, for all $n \in \mathbb{N}$, $$1 + r + r^2 + \dots + r^{n-1} = \frac{r^n - 1}{r - 1}, \quad r \neq 1.$$
Prove by induction that, for all $n \in \mathbb{N}$,
$$1 + r + r^2 + \dots + r^{n-1} = \frac{r^n - 1}{r - 1}, \quad r \neq 1.$$Prove by induction that, for all $n \in \mathbb{N}$, $$1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}.$$
Prove by induction that, for all $n \in \mathbb{N}$,
$$1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}.$$Prove by induction that, for all $n \in \mathbb{N}$, $$\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \dots + \frac{1}{n(n+1)} = \frac{n}{n+1}.$$
Prove by induction that, for all $n \in \mathbb{N}$,
$$\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \dots + \frac{1}{n(n+1)} = \frac{n}{n+1}.$$Proving divisibility
To show that an expression $f(n)$ is divisible by $m$, the statement is $P(n)$: "$f(n)$ is divisible by $m$", meaning $f(n) = m \times$ (some integer).
In the inductive step, the assumption is $f(k) = m\,t$ for some integer $t$. You then rewrite $f(k+1)$ so that a copy of $f(k)$ appears, plus something obviously divisible by $m$.
There are two standard ways to split $f(k+1)$. For $7^n - 1$ and divisor 6, write $7^{k+1} - 1 = 7(7^k - 1) + 6$. Alternatively, substitute $7^k = 6t + 1$ directly: $7^{k+1} - 1 = 7(6t+1) - 1 = 42t + 6 = 6(7t+1)$.
Prove by induction that $4^n - 1$ is divisible by 3 for all $n \in \mathbb{N}$. Begin by checking the case $n = 1$, then show that $4^{k+1} - 1 = 4(4^k - 1) + 3$.
Prove by induction that $4^n - 1$ is divisible by 3 for all $n \in \mathbb{N}$. Begin by checking the case $n = 1$, then show that $4^{k+1} - 1 = 4(4^k - 1) + 3$.
Prove by induction that $7^n - 1$ is divisible by 6 for all $n \in \mathbb{N}$.
Prove by induction that $7^n - 1$ is divisible by 6 for all $n \in \mathbb{N}$.
Prove by induction that $5^n + 2\cdot 11^n$ is divisible by 3 for all $n \in \mathbb{N}$.
Prove by induction that $5^n + 2\cdot 11^n$ is divisible by 3 for all $n \in \mathbb{N}$.
Induction and De Moivre's Theorem
Induction also proves results about complex numbers. De Moivre's Theorem says that, for $n \in \mathbb{N}$,
$$(\cos\theta + i\sin\theta)^n = \cos n\theta + i\sin n\theta.$$The inductive step needs the addition formulae (you will find these in the Formulae and Tables booklet):
$$\cos(A+B) = \cos A\cos B - \sin A \sin B, \qquad \sin(A+B) = \sin A\cos B + \cos A\sin B.$$Let $z = \cos\theta + i\sin\theta$. Prove by induction that $z^n = \cos n\theta + i\sin n\theta$ for all $n \in \mathbb{N}$, stating clearly which trigonometric addition…
Let $z = \cos\theta + i\sin\theta$. Prove by induction that $z^n = \cos n\theta + i\sin n\theta$ for all $n \in \mathbb{N}$, stating clearly which trigonometric addition formulae you use. Hence evaluate $\left(\cos\frac{\pi}{12} + i\sin\frac{\pi}{12}\right)^{6}$.
Back to the start: the dominoes at the clubhouse all fall because the first one falls and each one knocks over the next. In the same way, $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ holds for every $n$, because it holds for $n = 1$ and truth at $k$ forces truth at $k+1$.
Summary
-
Induction proves $P(n)$ for all $n \in \mathbb{N}$ in three steps: base case $P(1)$, inductive step ($P(k) \Rightarrow P(k+1)$), conclusion.
-
For sums, add the $(k+1)$th term to both sides of $P(k)$, then factorise to reach the target.
-
For divisibility, assume $f(k) = m\,t$ with $t$ an integer, and rewrite $f(k+1)$ as a multiple of $f(k)$ plus a multiple of $m$.
-
De Moivre's Theorem is proved by multiplying by $\cos\theta + i\sin\theta$ and using the addition formulae.
-
Always write $P(k)$ and $P(k+1)$ first, and finish with a clear conclusion sentence.