Base case and induction hypothesis | Year 12

01 / LEARN

The idea, step by step

A statement with a domain

Induction proves an infinite family of integer statements. Define P(n) and the smallest allowed integer before doing algebra. Substitute that first integer into both sides of an identity, or check divisibility directly.

One example does not establish infinitely many cases. The starting case is only the first of two obligations; the other is a successor implication valid at an arbitrary integer.

A conditional assumption

Assume P(k) for one arbitrary integer k in the allowed domain. This assumption belongs inside a conditional argument, not at the beginning of a claim that every P(n) is already true.

After proving P(k) implies P(k+1), the checked starting case begins the chain. A calculation with only k=4 proves one link, not a general implication.

A common trap

Assuming the result for all n.

Instead: Assume only one arbitrary kth case while proving the conditional step.

02 / WORKED EXAMPLES

See the thinking

Example 1

A sum identity

Prove $1 + 2 + \dots + n = n (n + 1) / 2$ for $n \geq 1$ .

At $n = 1$ , both sides are $1$ .
Assume the sum to arbitrary integer $k \geq 1$ is $k (k + 1) / 2$ .
Add the next term $k + 1$ .
The next sum is $k (k + 1) / 2 + (k + 1) = (k + 1) (k + 2) / 2$ .
Conclude all positive integers by induction.

1 + 2 + \dots + n = n (n + 1) / 2

is true throughout the stated domain.

Example 2

Divisibility

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

$n = 1$ gives $4$ .
Assume $5^{k} - 1 = 4 q$ for an integer $q$ .
Write $5^{k + 1} - 1 = 5 (5^{k} - 1) + 4$ .
This is $4 (5 q + 1)$ , an integer multiple of $4$ .
Conclude all positive integers by induction.

5^{n} - 1

is divisible by

4

is true throughout the stated domain.

Check your understanding

For a statement covering n at least 3, which base case is required?

Show answer

n=3.

Induction starts at the first allowed integer.

03 / WORKSHEET

Your turn

6 questions · 13 marks · Work at your own pace.

Worksheet PDF 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} = 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} = 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} = 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…

Continue learning

Constructing the induction step

Next lesson

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 ↗

Back to Mathematical induction