# Proof by Mathematical Induction

> Prove a statement is true for every whole number with two steps, the base case and the inductive step. Sums and divisibility.

From HSC Maths Extension 1 on WhizzNotes, free study notes for NSW students: https://whizznotes.com/mathematics-extension-1/mathematical-induction/. Updated 3 November 2026.
Year 11 and Year 12 boxes go deeper than the Year 10 text around them.

### Story time: The dominoes
Imagine a row of dominoes stretching forever. You want to be sure every single one falls. You cannot push them all. But if you know two things, you are certain:

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

Then the first knocks the second, the second knocks the third, and so on forever. **Mathematical induction** proves statements about all whole numbers in exactly this way.

**In short:** Mathematical induction proves a statement for every whole number in two steps. First, prove it is true for the first value. Then show that if it is true for $n = k$, it must also be true for $n = k + 1$, so it is true for all of them.

## Starting point: what you already know

- **Sigma notation:** $\displaystyle\sum_{k=1}^{n} k = 1 + 2 + \dots + n$.
- From arithmetic series: $1 + 2 + \dots + n = \dfrac{n(n + 1)}{2}$.
- **Divisible by 3** means equal to $3M$ for some whole number $M$.
- Algebra skills: factorising, expanding, finding a common denominator.

## Why we need proof

The pattern $1 = 1^2$, $1 + 3 = 2^2$, $1 + 3 + 5 = 3^2$ suggests that the first $n$ odd numbers add to $n^2$. Checking more examples makes it believable, but checking a million cases still does not prove it for the next one. Induction proves it for **every** $n$ at once.

## The structure

Let $P(n)$ be the statement you want to prove.

### Key idea: The two steps
1. **Base case.** Show $P(1)$ is true. (Start at whatever first value the question says.)
2. **Inductive step.** Assume $P(k)$ is true for some whole number $k$. Use this to show $P(k + 1)$ is true.

**Conclusion.** By the principle of mathematical induction, $P(n)$ is true for all whole numbers $n \ge 1$.

The assumption in step 2 is called the **inductive hypothesis**. You are not assuming what you want to prove. You are proving "if it works for one domino, it works for the next".

## Proving sums

### Worked example: Prove 1 + 3 + 5 + ... + (2n − 1) = n² for n ≥ 1
**Base case** $n = 1$: left side $= 1$, right side $= 1^2 = 1$. True.

**Inductive step.** Assume it is true for $n = k$:
$$1 + 3 + \dots + (2k - 1) = k^2$$
Prove it for $n = k + 1$, that is:
$$1 + 3 + \dots + (2k - 1) + (2k + 1) = (k + 1)^2$$
$$\begin{aligned} \text{Left side} &= k^2 + (2k + 1) \quad \text{by the assumption} \\ &= (k + 1)^2 = \text{right side} \end{aligned}$$

**Conclusion.** True for $n = 1$, and true for $n = k + 1$ whenever true for $n = k$. So by induction it is true for all $n \ge 1$.

### Exam tip: Write the target first
Always write out what $P(k + 1)$ says before you start. Then you know exactly what you are aiming for.

## Proving divisibility

### Worked example: Prove 5ⁿ − 1 is divisible by 4 for n ≥ 1
**Base case** $n = 1$: $5 - 1 = 4 = 4 \times 1$. True.

**Inductive step.** Assume $5^k - 1 = 4M$ for some whole number $M$, so $5^k = 4M + 1$.

Prove $5^{k+1} - 1$ is divisible by 4:
$$5^{k+1} - 1 = 5 \cdot 5^k - 1 = 5(4M + 1) - 1 = 20M + 4 = 4(5M + 1)$$
Since $5M + 1$ is a whole number, this is divisible by 4.

**Conclusion.** By induction, $5^n - 1$ is divisible by 4 for all $n \ge 1$.

### Watch out: Both steps are needed
Missing either step breaks the proof.

- The claim $n + 1 > n + 2$ passes the inductive step, since adding 1 to both sides of $k + 1 > k + 2$ gives $k + 2 > k + 3$. But it is never true. There is no first domino.
- The claim that $n^2 - n + 41$ is always prime works for $n = 1$ to 40 but fails at $n = 41$, since $41^2$ is not prime. A base case alone proves nothing.

**Mind map**

```text
Mathematical induction
  Idea
    First domino falls
    Each one knocks the next
  Steps
    Base case n = 1
    Assume true for n = k
    Prove for n = k + 1
    Write the conclusion
  Sums
    Add the next term to both sides
  Divisibility
    Write as divisor × M
    Substitute and factor
  Errors
    No base case
    Inductive step fails
```

### Year 11: Sigma notation review
$\displaystyle\sum_{r=1}^{n} r^2 = 1^2 + 2^2 + \dots + n^2$. To go from $n = k$ to $n = k + 1$ you add exactly **one** more term, $(k + 1)^2$.

### Year 12: A harder sum
Prove $\displaystyle\sum_{r=1}^{n} r^2 = \frac{n(n + 1)(2n + 1)}{6}$.

**Base case:** $1 = \dfrac{1 \cdot 2 \cdot 3}{6}$. True.

**Step.** Assume $\displaystyle\sum_{r=1}^{k} r^2 = \frac{k(k + 1)(2k + 1)}{6}$. Then
$$\sum_{r=1}^{k+1} r^2 = \frac{k(k + 1)(2k + 1)}{6} + (k + 1)^2 = \frac{(k + 1)\big[k(2k + 1) + 6(k + 1)\big]}{6}$$
$$= \frac{(k + 1)(2k^2 + 7k + 6)}{6} = \frac{(k + 1)(k + 2)(2k + 3)}{6}$$
which is the formula with $n = k + 1$. **Tip:** take out the common factor $(k + 1)$ early instead of expanding everything.

**Fractions.** For $\sum_{r=1}^{n}\frac{1}{r(r + 1)} = \frac{n}{n + 1}$, the step is $\dfrac{k}{k + 1} + \dfrac{1}{(k + 1)(k + 2)} = \dfrac{k(k + 2) + 1}{(k + 1)(k + 2)} = \dfrac{(k + 1)^2}{(k + 1)(k + 2)} = \dfrac{k + 1}{k + 2}$. Use the common denominator, then factorise the top. With factorials, write both fractions over the larger factorial, using $(k + 3)! = (k + 3)(k + 2)!$.

**Inequalities.** To prove $3^n > 2n + 1$ for $n \geq 2$: the base case is $9 > 5$. Assume $3^k > 2k + 1$. Then $3^{k+1} = 3 \times 3^k > 3(2k + 1) = 6k + 3 > 2k + 3 = 2(k + 1) + 1$, since $6k > 2k$. First check small values to find where the statement starts to be true: $2^n > n^2$ fails at $n = 3$ and $n = 4$ ($16 = 16$), and works from $n = 5$.

**Trig sums.** In the step, a product-to-sum identity often turns the new term into a difference of squares of sines, such as $\sin(2k + 1)\theta\sin\theta = \sin^2(k + 1)\theta - \sin^2 k\theta$.

### Year 12: A harder divisibility proof
Prove $7^n + 2$ is divisible by 3. Base: $9 = 3 \times 3$. Assume $7^k + 2 = 3M$, so $7^k = 3M - 2$. Then
$$7^{k+1} + 2 = 7(3M - 2) + 2 = 21M - 12 = 3(7M - 4)$$

**An extra fact.** Sometimes the leftover terms need one more fact. Proving $n^3 + 2n$ is divisible by 3: $(k + 1)^3 + 2(k + 1) = (k^3 + 2k) + 3k^2 + 3k + 3$, and every part is a multiple of 3. For $n^3 + 5n$ and 6, the leftover is $3k(k + 1) + 6$, and $k(k + 1)$ is even (one of two neighbours is even), so $3k(k + 1)$ is a multiple of 6.

**More than one term.** For $9^n - 1 - 8n$ divisible by 64: assume $9^k = 64M + 1 + 8k$, then $9^{k+1} - 1 - 8(k + 1) = 9(64M + 1 + 8k) - 9 - 8k = 576M + 64k = 64(9M + k)$.

## Quick summary

- Induction has two steps: prove the base case, then show that if it is true for $k$, it is true for $k + 1$.
- For sums, add the next term to the assumed sum and simplify to the target.
- For divisibility, write the assumption as divisor $\times M$, substitute, then factor out the divisor.
- Finish with the conclusion sentence. Missing either step means there is no proof.

## Quiz

Try these questions from the chapter quiz.

1. The first step of a proof by induction is to:
   - A. prove the statement for the first value, usually $n = 1$
   - B. assume the statement is true for all $n$
   - C. prove it for $n = k + 1$
   - D. check 10 examples
   - Answer: A. prove the statement for the first value, usually $n = 1$. This is the base case: the first domino falls.

2. In the inductive step you assume the statement is true for:
   - A. all $n$
   - B. $n = k$
   - C. $n = k + 1$
   - D. $n = 0$ only
   - Answer: B. $n = k$. Then you show it must also be true for $n = k + 1$.

3. Why does checking many examples not prove a statement?
   - A. examples are always wrong
   - B. the next case might still fail
   - C. induction does not use examples
   - D. it takes too long
   - Answer: B. the next case might still fail. A pattern can hold for many cases and then break.

The whole chapter quiz is on the page, for signed-in students: https://whizznotes.com/mathematics-extension-1/mathematical-induction/#quiz