Prove statements about sums, divisibility and inequalities for all positive integers using the principle of mathematical induction

What this dot point is asking

SEAB wants you to prove that a statement $P_n$ holds for every positive integer $n$ using the principle of mathematical induction. You must verify a base case, assume the statement for an arbitrary $k$, and deduce it for $k+1$, then conclude that it holds for all $n$. The three families you must be able to handle are summation formulae, divisibility results, and inequalities.

The answer

The principle of mathematical induction

Let $P_n$ be a statement depending on a positive integer $n$. The principle says: if

1. $P_1$ is true (the base case), and
2. for every positive integer $k$, the truth of $P_k$ implies the truth of $P_{k+1}$ (the inductive step),

then $P_n$ is true for all positive integers $n$. The intuition is a chain of dominoes: the base case knocks over the first, and the inductive step guarantees each domino topples the next.

The structure every proof must show

A complete induction proof has four written parts:

• Define $P_n$ precisely as a statement (not just "the formula").
• Base case: verify $P_1$ (or whatever the smallest relevant integer is) by direct computation.
• Inductive step: state the inductive hypothesis "assume $P_k$ is true for some positive integer $k$", then derive $P_{k+1}$ from it.
• Conclusion: a sentence of the form "since $P_1$ is true and $P_k \Rightarrow P_{k+1}$, by the principle of mathematical induction $P_n$ is true for all positive integers $n$."

Summation proofs

For a result such as $\sum_{r=1}^{n} u_r = \mathrm{S}(n)$, the inductive step splits off the last term:

You then do algebra to show this equals $\mathrm{S}(k+1)$, the formula with $n$ replaced by $k+1$. Knowing the target $\mathrm{S}(k+1)$ in advance tells you what to factor towards.

Divisibility proofs

For "$f(n)$ is divisible by $d$", write the hypothesis as $f(k) = d\,m$ for some integer $m$. In the step, manipulate $f(k+1)$ to expose a copy of $f(k)$ (or $d\,m$) plus a multiple of $d$, then factor out $d$ leaving an integer.

Inequality proofs

For "$f(n) > g(n)$" (or $\geq$), use the hypothesis $f(k) > g(k)$ and a chain of inequalities. The key move is often: $f(k+1) = f(k) + (\text{something}) > g(k) + (\text{something}) \geq g(k+1)$, where the last step needs a small side-argument.

Examples in context

Example 1. Deriving a result you will reuse. The sum $\sum_{r=1}^{n} r^2 = \tfrac{1}{6}n(n+1)(2n+1)$ is proved by induction and then used freely in the summation-of-series work. Induction is how the standard results are placed on a rigorous footing before they become tools.

Example 2. Validating a recurrence's closed form. When a recurrence relation is solved and a closed formula is proposed for $u_n$, induction is the natural way to prove that the formula satisfies both the initial condition and the recurrence, confirming it for all $n$.

Try this

Q1. State the two things you must establish in a proof by mathematical induction. [2 marks]

• Cue. A true base case ($P_1$), and the implication that $P_k$ true implies $P_{k+1}$ true for all positive integers $k$.

Q2. In proving $\sum_{r=1}^{n} r = \tfrac{1}{2}n(n+1)$, write the expression for $\sum_{r=1}^{k+1} r$ using the inductive hypothesis. [2 marks]

• Cue. $\sum_{r=1}^{k+1} r = \tfrac{1}{2}k(k+1) + (k+1)$, which factors to $\tfrac{1}{2}(k+1)(k+2)$.

Q3. When proving $7^n - 1$ is divisible by $6$, how should you write the inductive hypothesis? [1 mark]

• Cue. Assume $7^k - 1 = 6m$ for some integer $m$, so $7^k = 6m + 1$.