What is not using the hypothesis?

A valid inductive step must actually substitute the assumed P(k); otherwise it is not induction.

§-Syllabus dot point

WASpecialist MathematicsSyllabus dot point

How does proving a base case and an inductive step establish a statement for every natural number?

Prove statements by mathematical induction, including summation, divisibility and inequality results

WACE Specialist proof by mathematical induction: the base case and inductive step, the structure of a rigorous induction, and applying it to summation formulas, divisibility statements and inequalities, with a worked example.

Generated by Claude Opus 4.88 min answerUpdated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
The structure of an induction
Summation proofs
Why induction proves a statement for all n
Divisibility proofs
Inequality proofs
How to set out a proof for full marks
The algebra of the inductive step

What this dot point is asking

SCSA wants a rigorously structured induction: a clear base case, an explicit hypothesis, a worked inductive step that uses the hypothesis, and a concluding statement.

The structure of an induction

The logic is a chain: the base case starts it, and the inductive step passes truth from each integer to the next, so every integer from $n_0$ upward is reached.

Summation proofs

For a claimed sum formula, the base case checks $n = 1$ . The inductive step adds the $(k+1)$ th term to the assumed sum for $k$ and shows the total matches the formula at $k+1$ . The key algebra is to factor and rearrange the expression for $k$ plus the new term into the target form.

Why induction proves a statement for all n

The logical force of induction is sometimes called the domino principle. The base case knocks over the first domino, and the inductive step guarantees that each fallen domino knocks over the next. Together they ensure every domino from the first onward falls, that is, $P(n)$ is true for every integer $n \ge n_0$ . Neither step alone is enough: a true base case without the inductive step says nothing about later values, and a valid inductive step without a base case has no starting point and proves nothing. This is why SCSA insists on both steps and a clear concluding statement.

Divisibility proofs

To show an expression is divisible by $d$ for all $n$ , assume $P(k)$ means the expression at $k$ is a multiple of $d$ . Then write the expression at $k+1$ so that it contains the expression at $k$ (a multiple of $d$ by hypothesis) plus an extra term that is also a multiple of $d$ . The sum is then divisible by $d$ .

Inequality proofs

For an inequality, the inductive step starts from the assumed inequality at $k$ and adds or multiplies a term to reach the $k+1$ form, often showing the difference of the two sides has a definite sign.

How to set out a proof for full marks

SCSA marks induction on structure as much as on algebra, so a disciplined layout matters. Begin by naming the statement: "Let $P(n)$ be the statement that ...". Verify the base case explicitly, computing both sides at the smallest value and stating that they agree. State the inductive hypothesis as "Assume $P(k)$ is true for some integer $k \ge n_0$ ", writing out exactly what is being assumed. Then aim to derive $P(k+1)$ , making the moment where the hypothesis is substituted clearly visible. Finish with the conclusion: "Hence by the principle of mathematical induction, $P(n)$ is true for all integers $n \ge n_0$ ." Omitting the base case, the explicit hypothesis, or the closing statement each costs marks even if the algebra is correct.

The algebra of the inductive step

The technical heart of a summation proof is rewriting the expression for $k$ plus the new term into the target form for $k+1$ . The reliable method is to take a common factor out of the assumed sum and the new term. In the sum-of-squares proof, both $\dfrac{k(k+1)(2k+1)}{6}$ and $(k+1)^2$ share the factor $(k+1)$ , so factoring it out leaves a quadratic in $k$ to simplify. For a divisibility proof, the key move is to write the expression at $k+1$ in terms of the expression at $k$ : for $7^{k+1} - 1$ , rewrite as $7 \cdot 7^k - 1$ and substitute $7^k = 6m + 1$ from the hypothesis. Recognising which algebraic manipulation exposes the hypothesis is the skill that separates a complete proof from a stalled one.

Worked example

Prove by induction that $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ for all $n \ge 1$ .

Step 1: Name the statement

Giving the statement a name lets us refer to it precisely in every subsequent step. Let $P(n)$ be the statement that the sum of the first $n$ positive integers equals $\tfrac{n(n+1)}{2}$ .

Step 2: Verify the base case

The base case anchors the chain of reasoning; without it, there is nothing to build from. For $n = 1$ , the left side is $1$ and the right side is $\tfrac{1 \times 2}{2} = 1$ . Both sides agree, so $P(1)$ is true.

Step 3: Establish the inductive step

We assume $P(k)$ is true for some integer $k \ge 1$ and aim to deduce $P(k+1)$ . We assume $1 + 2 + \dots + k = \tfrac{k(k+1)}{2}$ and add the next term $k + 1$ to both sides:

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

This is exactly the formula with $n = k + 1$ , so $P(k+1)$ is true whenever $P(k)$ is true.

Step 4: State the conclusion

Both conditions of the principle of mathematical induction have been satisfied: the base case holds and the inductive step is valid. By induction, $P(n)$ holds for all integers $n \ge 1$ .

Final answer: $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ for all integers $n \ge 1$ .

Exam-style practice questions

Practice questions written in the style of SCSA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

WACE 20237 marksCalculator-free. Prove by mathematical induction that

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

for all integers

n \ge 1

Show worked answer →

A standard summation induction.

Let $P(n)$ be the statement $\sum_{r=1}^{n} r^2 = \dfrac{n(n+1)(2n+1)}{6}$ .

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

Inductive step: assume $P(k)$ , that $\sum_{r=1}^{k} r^2 = \dfrac{k(k+1)(2k+1)}{6}$ . Add the next term $(k+1)^2$ : $\dfrac{k(k+1)(2k+1)}{6} + (k+1)^2 = \dfrac{(k+1)\big[k(2k+1) + 6(k+1)\big]}{6} = \dfrac{(k+1)(2k^2 + 7k + 6)}{6} = \dfrac{(k+1)(k+2)(2k+3)}{6}$ . This is $P(k+1)$ , the formula with $n = k+1$ .

By induction $P(n)$ holds for all $n \ge 1$ . Markers reward the base case, the explicit hypothesis, the factorisation to the $k+1$ form, and the concluding statement.

WACE 20216 marksCalculator-free. Prove by mathematical induction that

7^n - 1

is divisible by

6

for all integers

n \ge 1

Show worked answer →

A divisibility induction.

Let $P(n)$ be the statement that $7^n - 1$ is divisible by $6$ .

Base case $n = 1$ : $7^1 - 1 = 6$ , divisible by $6$ . True.

Inductive step: assume $P(k)$ , so $7^k - 1 = 6m$ for some integer $m$ , i.e. $7^k = 6m + 1$ . Then $7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(6m + 1) - 1 = 42m + 7 - 1 = 42m + 6 = 6(7m + 1)$ , a multiple of $6$ . So $P(k+1)$ holds.

By induction $7^n - 1$ is divisible by $6$ for all $n \ge 1$ . Markers reward the base case, expressing $7^k$ from the hypothesis, factoring out $6$ at $k+1$ , and the conclusion.