Proof by mathematical induction: VCE Specialist Mathematics Unit 3

What this dot point is asking

VCAA wants you to prove statements about all positive integers using mathematical induction, setting out the base step, the inductive assumption and the inductive step clearly, and reaching a correct conclusion. The method applies to summation formulas, divisibility claims and inequalities. Marks are awarded for structure as much as for algebra, so the layout matters.

The principle

To prove a proposition $P(n)$ for all integers $n \ge n_0$:

1. Base step. Show $P(n_0)$ is true by direct substitution.
2. Inductive step. Assume $P(k)$ is true for some integer $k \ge n_0$ (this is the inductive assumption), and prove that $P(k + 1)$ follows.
3. Conclusion. By the principle of mathematical induction, $P(n)$ is true for all $n \ge n_0$.

The logic is a chain of dominoes: the base knocks over $P(n_0)$, and the inductive step guarantees each true case topples the next, so every case falls.

Three standard families

Summation formulas

To prove $\sum_{r=1}^{n} a_r = S(n)$, the inductive step adds the $(k+1)$th term to the assumed sum $S(k)$ and simplifies to $S(k+1)$.

Divisibility

To prove that an expression is divisible by $d$, write the assumption as "the expression at $k$ equals $d \times (\text{integer})$", then rearrange the $k+1$ expression to expose a factor of $d$.

Inequalities

To prove $f(n) \ge g(n)$, use the assumption $f(k) \ge g(k)$ and bound the extra growth from $k$ to $k+1$.

Writing it well

Always state explicitly "Assume true for $n = k$", write down exactly what that means, and signal where you use it in the $k+1$ working. End with a sentence invoking the principle of induction. A proof that omits the base step, or that never uses the assumption, earns few marks even if the algebra is right.

Examples in context

Example 1 (divisibility). To show $3^n - 1$ is divisible by $2$: at $k+1$, $3^{k+1} - 1 = 3(3^k - 1) + 2$, and the assumption makes $3^k - 1$ even, so the whole expression is even.

Example 2 (inequality). To show $2^n > n$ for $n \ge 1$: from $2^k > k$, $2^{k+1} = 2\cdot 2^k > 2k \ge k + 1$ for $k \ge 1$.

Try this

Q1. State the three parts of a proof by mathematical induction. [2 marks]

• Cue. Base step, inductive step using the inductive assumption, and a conclusion by the principle of induction.

Q2. Verify the base step for $\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}$ at $n = 1$. [2 marks]

• Cue. Left side $1$; right side $\frac{1\cdot 2\cdot 3}{6} = 1$.

Q3. In proving $5^n - 1$ is divisible by $4$, write the inductive assumption. [1 mark]

• Cue. $5^k - 1 = 4m$ for some integer $m$.