Introduction to proof by induction | Year 11

01 / LEARN

The idea, step by step

Start a chain, then prove every link

Checking several integers suggests a conjecture but does not prove a statement about all positive integers. Induction verifies the smallest allowed case and shows that any true case forces the next.

The induction hypothesis is an assumption about one arbitrary permitted integer $k$ . Do not assume the entire conclusion or the case $k + 1$ . The task is to derive that next case.

Show the algebra that makes the next case

Begin the step with the next sum or recurrence expression, separate its new term and apply the hypothesis only to the part it describes. Transform the expression into the target next-case formula.

Conclude the correct domain: a proof beginning at $n = 3$ establishes integers from 3 onwards, not the missing cases 1 and 2. Both the base and implication are essential.

A common trap

The induction hypothesis lets you assume the $k + 1$ case.

Instead: Assume the $k$ case only; assuming the next case is circular.

02 / WORKED EXAMPLES

See the thinking

Example 1

A sum of odd numbers

Prove $1 + 3 + \dots + (2 n - 1) = n^{2}$ for $n \geq 1$ .

Base $n = 1$ : both sides equal 1.
Assume the first $k$ odd numbers sum to $k^{2}$ .
Adding $2 k + 1$ gives ${(k + 1)}^{2}$ ; conclude by induction.

True for all integers

n \geq 1

Example 2

A recurrence identity

$u_{1} = 3, u_{n + 1} = u_{n} + 2$ . Prove $u_{n} = 2 n + 1$ .

Base: $3 = 2 (1) + 1$ .
Assume $u_{k} = 2 k + 1$ . Then $u_{k + 1} = 2 k + 3 = 2 (k + 1) + 1$ . Conclude by induction.

True for all integers

n \geq 1

Check your understanding

A proof begins at 2 and gives a valid implication for every $k \geq 2$ . What is proved?

Show answer

All integers $n \geq 2$ .

The implication chain begins at 2.

03 / WORKSHEET

Your turn

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

Worksheet PDF Worked solutions

Read the questions online

Check the base case for $1 + 2 + \dots + n = n (n + 1) / 2$ .
2 marks
State the induction hypothesis for the same identity.
2 marks
Complete the induction step for the same identity.
3 marks
A student checks $n = 1, 2, 3$ and concludes an identity holds for every positive integer. Identify the missing argument.
2 marks
Prove $2 + 4 + \dots + 2 n = n (n + 1)$ by induction.
4 marks
Why is an induction step alone insufficient for $1 + 2 + \dots + n = n (n + 1) / 2 + 5$ ?
3 marks

Read the worked solutions

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

Check the base case for $1 + 2 + \dots + n = n (n + 1) / 2$ .
2 marks
The two sides agree for the first permitted integer.
At $n = 1$ , $1 = 1 (2) / 2$ .
State the induction hypothesis for the same identity.
2 marks
This assumes just the arbitrary $k$ case.
Assume $1 + 2 + \dots + k = k (k + 1) / 2$ for arbitrary integer $k \geq 1$ .
Complete the induction step for the same identity.
3 marks
Factor $(k + 1)$ from the two terms.
$k (k + 1) / 2 + (k + 1) = (k + 1) (k + 2) / 2$ .
A student checks $n = 1, 2, 3$ and concludes an identity holds for every positive integer. Identify the missing argument.
2 marks
Finite checks do not exclude later failure.
No implication for arbitrary $k$ to $k + 1$ has been established.
Prove $2 + 4 + \dots + 2 n = n (n + 1)$ by induction.
4 marks
Base: $2 = 1 (2)$ .
Assume $S_{k} = k (k + 1)$ . Add $2 (k + 1)$ to get $(k + 1) (k + 2)$ ; conclude.
True for all integers $n \geq 1$ .
Why is an induction step alone insufficient for $1 + 2 + \dots + n = n (n + 1) / 2 + 5$ ?
3 marks
A formal same-offset implication can hold without a true starting case.
The base fails: at $n = 1$ the sides are 1 and 6.

Checking saved progress…

Continue learning

Induction proofs of simple sums and arithmetic/geometric-series results

Next lesson

Curriculum reference & lesson scope

SACE Board of South Australia

Stage 1 Mathematics sequence and series content with introductory induction, regrouped into an original school-sized chapter.

Official curriculum source ↗

Back to Sequences and series