Proof by induction: identities and divisibility · Mathematics 5th Year HL

The domino idea

Suppose you notice that $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$ works for $n = 1, 2, 3, 4$. That is encouraging, but it is not a proof, because there are infinitely many values of $n$ still to check. Induction proves a statement $P(n)$ for every $n \in \mathbb{N} = \{1, 2, 3, \dots\}$ in one go.

A proof by induction has four parts. Always write all four.

Why does it work? $P(1)$ is true by step 1. Step 3 then gives $P(2)$, then $P(3)$, then $P(4)$, and so on, with no end. Each result knocks over the next one.

Proving formulae for sums

For a sum, $P(n)$ is a formula for $S_n$, the sum of the first $n$ terms. The key move in the inductive step is

$$S_{k+1} = S_k + T_{k+1},$$

so you replace $S_k$ by the formula you assumed, add the next term, and tidy up until you reach the formula with $k+1$ in place of $n$.

Prove that $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$ for all $n \in \mathbb{N}$

Base case. For $n = 1$: LHS $= 1$ and RHS $= \frac{1 \cdot 2}{2} = 1$. So $P(1)$ is true.

Assumption. Assume $P(k)$ is true: $1 + 2 + \dots + k = \frac{k(k+1)}{2}$.

Inductive step. We must prove $P(k+1)$, that is, $1 + 2 + \dots + (k+1) = \frac{(k+1)(k+2)}{2}$. Write the target down first so you know where you are heading.

Start with the left-hand side and use the assumption on the first $k$ terms:

$$1 + 2 + \dots + k + (k+1) = \frac{k(k+1)}{2} + (k+1).$$

Take out the common factor $(k+1)$:

$$\frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = (k+1)\cdot\frac{k+2}{2} = \frac{(k+1)(k+2)}{2}.$$

This is the right-hand side of $P(k+1)$.

Conclusion. $P(1)$ is true, and $P(k)$ true implies $P(k+1)$ true. Hence, by induction, $P(n)$ is true for all $n \in \mathbb{N}$. $\blacksquare$

Practice★☆☆

Prove by induction that for all $n\in\mathbb{N}$, $$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}.$$

Prove by induction that for all $n\in\mathbb{N}$,

$$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}.$$

Solve

Prove that $\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}$ for all $n \in \mathbb{N}$

Base case. $n = 1$: LHS $= 1^2 = 1$. RHS $= \frac{1 \cdot 2 \cdot 3}{6} = 1$. True.

Assumption. Assume $\sum_{r=1}^{k} r^2 = \frac{k(k+1)(2k+1)}{6}$.

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

Your turn. Add the term $(k+1)^2$ to the assumed formula, take out the common factor $(k+1)$, and see if you can reach the target before you read on.

$$\sum_{r=1}^{k+1} r^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{(k+1)\left[k(2k+1) + 6(k+1)\right]}{6}$$ $$= \frac{(k+1)(2k^2 + 7k + 6)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}.$$

since $2k^2 + 7k + 6 = (k+2)(2k+3)$.

Conclusion. $P(1)$ is true and $P(k) \Rightarrow P(k+1)$. Hence $P(n)$ is true for all $n \in \mathbb{N}$ by induction. $\blacksquare$

Practice★☆☆

Prove by induction that $\sum_{r=1}^{n} (2r-1) = n^2$ for all $n \in \mathbb{N}$.

Solve

Practice★★☆

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

Prove by induction that

$$\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}$$

for all $n\in\mathbb{N}$.

Solve

Proving divisibility

Now $P(n)$ says "$f(n)$ is divisible by $m$". In the assumption, write this as an equation: $f(k) = m \cdot t$ for some integer $t$. In the inductive step, you must rewrite $f(k+1)$ so that $f(k)$ appears in it, then show what is left over is also a multiple of $m$.

Practice★☆☆

Prove by induction that $4^n - 1$ is divisible by 3 for all $n\in\mathbb{N}$.

Solve

There is a second way to write the same step that is often quicker. Arrange $f(k+1)$ as a multiple of $f(k)$ plus a multiple of $m$:

$$4^{k+1} - 1 = 4(4^k - 1) + 3.$$

The first part is divisible by 3 by the assumption, and $3$ is divisible by 3, so the sum is.

Prove that $7^n - 3^n$ is divisible by 4 for all $n \in \mathbb{N}$

Base case. $n = 1$: $7 - 3 = 4$, divisible by 4. True.

Assumption. Assume $7^k - 3^k = 4t$ for some integer $t$.

Inductive step. We need $7^{k+1} - 3^{k+1}$ in terms of $7^k - 3^k$. Write $7^{k+1} = 7 \cdot 7^k$ and fix the $3$ part by adding and subtracting $7 \cdot 3^k$:

$$7^{k+1} - 3^{k+1} = 7\cdot 7^k - 7 \cdot 3^k + 7 \cdot 3^k - 3 \cdot 3^k = 7(7^k - 3^k) + 4 \cdot 3^k.$$

Your turn. Use the assumption to explain why the whole expression is divisible by 4, then write the conclusion.

By the assumption, $7(7^k - 3^k) = 28t$, which is a multiple of 4, and $4 \cdot 3^k$ is a multiple of 4. So $7^{k+1} - 3^{k+1} = 4(7t + 3^k)$ is divisible by 4.

Conclusion. By induction, $7^n - 3^n$ is divisible by 4 for all $n \in \mathbb{N}$. $\blacksquare$

Practice★★☆

Prove by induction that $7^n - 3^n$ is divisible by 4 for all $n \in \mathbb{N}$.

Solve

Practice★★★

Prove by induction that $n^3 + 2n$ is divisible by 3 for all $n\in\mathbb{N}$, and that $5^{2n} - 1$ is divisible by 24 for all $n\in\mathbb{N}$.

Solve

Trickier sums and sequences

Two situations need a little more care: sums whose terms are not simple polynomials, and sequences defined by a rule that links each term to the two before it.

Sums with fractions

When the inductive step involves fractions, put everything over a common denominator and look for a perfect square or a factor that cancels.

The same technique proves $\sum_{r=1}^{n} r \cdot 2^r = (n-1)2^{n+1} + 2$. There, after adding the term $(k+1)2^{k+1}$, factor out $2^{k+1}$.

Sequences defined by recurrence

A sequence such as $u_{n+2} = 5u_{n+1} - 6u_n$ is built from the two terms before. To prove a formula for $u_n$ you need two basis cases, and in the assumption you assume the formula for two consecutive terms. This is called strong induction.

Practice★★☆

Prove by induction that $\sum_{r=1}^{n} r\cdot 2^{r} = (n-1)2^{n+1} + 2$ for all $n\in\mathbb{N}$.

Solve

Practice★★★

Prove by induction that $$\sum_{r=1}^{n} \frac{1}{r(r+1)} = \frac{n}{n+1}$$ for all $n\in\mathbb{N}$. Hence evaluate $\sum_{r=1}^{\infty} \frac{1}{r(r+1)}$, justifying…

Prove by induction that

$$\sum_{r=1}^{n} \frac{1}{r(r+1)} = \frac{n}{n+1}$$

for all $n\in\mathbb{N}$. Hence evaluate $\sum_{r=1}^{\infty} \frac{1}{r(r+1)}$, justifying your answer.

Solve

Practice★★★

A sequence is defined by $u_1 = 1$, $u_2 = 5$ and $u_{n+2} = 5u_{n+1} - 6u_n$. a) Calculate $u_3$ and $u_4$. b) Conjecture a formula for $u_n$ in terms of powers of 2…

A sequence is defined by $u_1 = 1$, $u_2 = 5$ and $u_{n+2} = 5u_{n+1} - 6u_n$.

a) Calculate $u_3$ and $u_4$.
b) Conjecture a formula for $u_n$ in terms of powers of 2 and 3.
c) Prove your formula by induction (strong induction on two previous terms).

Solve

Let's practice! 9 exercises in this section

★☆☆ Prove by induction that for all $n\in\mathbb{N}$, $$1 + 2 + 3 + \dots + n =…★☆☆ Prove by induction that $\sum_{r=1}^{n} (2r-1) = n^2$ for all $n \in \mathbb{N}$.★☆☆ Prove by induction that $4^n - 1$ is divisible by 3 for all $n\in\mathbb{N}$.

Summary

Induction proves a statement $P(n)$ for all $n \in \mathbb{N}$ using: base case ($P(1)$), assumption ($P(k)$), inductive step ($P(k+1)$) and a conclusion.
For sums, use $S_{k+1} = S_k + T_{k+1}$, write the target first, and factorise rather than expand.
For divisibility, write the assumption as $f(k) = m t$, then rewrite $f(k+1)$ as a multiple of $f(k)$ plus a multiple of $m$ (for example $4^{k+1} - 1 = 4(4^k - 1) + 3$).
For a sequence defined by two previous terms, check two base cases and assume two consecutive terms.
Always finish with the full conclusion sentence: "$P(1)$ true and $P(k) \Rightarrow P(k+1)$, hence true for all $n \in \mathbb{N}$ by induction."
Leaving Cert style: if asked to hence evaluate an infinite sum, take the limit of the partial sums $S_n$ and state the answer.