Base case and induction hypothesis | Year 12

01 / LEARN

Understand the method.

THE CORE RULE

\begin{array}{c} P (n_{0}) is true \\ P (k) ⟹ P (k + 1) (k \geq n_{0}) \end{array}

The base case starts the chain. The successor implication carries it through every integer in the stated domain.

State exactly what is being proved

Call the statement $P (n)$ and state its integer domain. The smallest allowed integer determines the base case.

Check that first case directly. A true starting case is necessary, but it does not establish all the later cases.

Assume one arbitrary case

Assume $P (k)$ for one arbitrary integer $k$ in the domain. This is the induction hypothesis.

Use that hypothesis to establish $P (k + 1)$ . Do not assume the next case or assume the result for every integer.

Make the successor match the statement

Write the target expression with $k + 1$ in place of $n$ . It tells you what your algebra must reach.

After checking the base case and proving the implication for arbitrary $k$ , conclude that the statement holds for every integer in the domain.

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

02 / WORKED EXAMPLES

See the method in action.

EXAMPLE 01

A sum identity

Prove $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ for integers $n \geq 1$ .

Worked solution

1
Check the base case.
$n = 1 : q q u a d 1 = \frac{1 (1 + 1)}{2}$
Both sides equal $1$ , so the first allowed case is true.
2
State the induction hypothesis.
$1 + 2 + \dots + k = \frac{k (k + 1)}{2}$
Assume this holds for one arbitrary integer $k \geq 1$ .
3
Add the next term and simplify.
$\begin{aligned} 1 + 2 + \dots + k + (k + 1) & = \frac{k (k + 1)}{2} + (k + 1) \\ = \frac{k (k + 1) + 2 (k + 1)}{2} \\ = \frac{(k + 1) (k + 2)}{2} \end{aligned}$
Use the hypothesis only for the sum to $k$ . The additional term is $k + 1$ .
4
Conclude for the stated domain.
$P (1) and P (k) ⟹ P (k + 1)$
The checked base and arbitrary successor step establish the identity for all positive integers.

Answer

$1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ for every integer $n \geq 1$ , by mathematical induction.

EXAMPLE 02

Divisibility

Prove $5^{n} - 1$ is divisible by $4$ for integers $n \geq 1$ .

Worked solution

1
Check the base case.
$5^{1} - 1 = 4$
The first allowed case is a multiple of $4$ .
2
State the induction hypothesis.
$5^{k} - 1 = 4 q, q \in ℤ$
Assume divisibility for one arbitrary integer $k \geq 1$ .
3
Expose the assumed multiple of four.
$\begin{aligned} 5^{k + 1} - 1 & = 5 (5^{k} - 1) + 4 \\ = 5 (4 q) + 4 \\ = 4 (5 q + 1) \end{aligned}$
The quantity $5 q + 1$ is an integer, so the next case is also divisible by $4$ .
4
Conclude by induction.
$4 ∣ (5^{n} - 1) for every integer n \geq 1$
The base case and successor implication cover every integer in the domain.

Answer

$5^{n} - 1$ is divisible by $4$ for every integer $n \geq 1$ .

03 / YOUR TURN

Try it yourself.

Calculate, explain, then apply.

CHECK 01

Choose the base case

For a statement covering integers $n \geq 3$ , which base case is required?

Show answer & reasoning

$n = 3$ .

Start at the first integer in the stated domain; starting later leaves earlier allowed cases unproved.

Keep practising

6 worksheet questions · 13 marks

Open worksheet Worked solutions

Read the questions online

Check the base case for $1 + 3 + \dots + (2 n - 1) = n^{2}$ , for $n \geq 1$ .
2 marks
State the induction hypothesis for $\sum_{r = 1}^{n} r^{2} = \frac{n (n + 1) (2 n + 1)}{6}$ .
2 marks
Check the first case of $3^{n} - 1$ even for integers $n \geq 0$ .
2 marks
For positive integers $n$ , write the induction hypothesis for $n^{3} - n$ divisible by six.
2 marks
A theorem is stated for $n$ at least 4, but the proof starts at $n = 5$ . Which case is omitted?
2 marks
Why is an induction hypothesis not an assumption that the whole theorem is true?
3 marks

Read the worked solutions

Equivalent correct methods earn the corresponding marks. Include units where asked.

Check the base case for $1 + 3 + \dots + (2 n - 1) = n^{2}$ , for $n \geq 1$ .
2 marks
Both sides equal 1.
At $n = 1$ , $1 = 1^{2}$ .
State the induction hypothesis for $\sum_{r = 1}^{n} r^{2} = \frac{n (n + 1) (2 n + 1)}{6}$ .
2 marks
Use $k$ consistently in every position.
Do not assume the next case.
For arbitrary integer $k \geq 1$ , assume $\sum_{r = 1}^{k} r^{2} = \frac{k (k + 1) (2 k + 1)}{6}$ .
Check the first case of $3^{n} - 1$ even for integers $n \geq 0$ .
2 marks
The smallest allowed integer is 0.
Zero is even.
At $n = 0$ , $3^{0} - 1 = 0 = 2 (0)$ .
For positive integers $n$ , write the induction hypothesis for $n^{3} - n$ divisible by six.
2 marks
The integer condition on $q$ expresses divisibility.
Assume $k^{3} - k = 6 q$ for some integer $q$ and arbitrary integer $k \geq 1$ .
A theorem is stated for $n$ at least 4, but the proof starts at $n = 5$ . Which case is omitted?
2 marks
The successor implication cannot run backward.
$n = 4$ .
Why is an induction hypothesis not an assumption that the whole theorem is true?
3 marks
$P (k)$ is assumed temporarily for arbitrary $k$ .
The base case and successor implication together establish every required case.
It is the premise in one conditional implication.

Checking saved progress…

Curriculum reference & lesson scope

SACE Board of South Australia

Stage 2 Specialist mathematical induction. Explicit summation, power and divisibility identities; induction of inequalities or recursive formulae is not required.

Official curriculum source ↗

In this lesson

Understand the method.

State exactly what is being proved

Assume one arbitrary case

Make the successor match the statement

See the method in action.

A sum identity

Check the base case.

State the induction hypothesis.

Add the next term and simplify.

Conclude for the stated domain.