Introduction to proof by induction | Year 11

01 / LEARN

Understand the idea.

Start a chain, then prove every link

Induction proves a statement for every integer in a consecutive domain. Verify the first case, then prove that if the statement holds at any permitted index $k$ , it must hold at $k + 1$ . The base starts the chain and the implication carries it onward.

The induction hypothesis assumes only the statement at one arbitrary $k$ . It does not grant the next case or assume the conclusion for every index. Checking many examples supplies evidence but cannot replace the general implication.

Show the algebra that makes the next case

Write the target expression for index $k + 1$ , then build it from the $k$ expression and one new term. Apply the hypothesis to the known part and show the algebra that produces the exact next-case formula.

End by naming the proved domain. A proof based at one reaches all positive integers; a proof based at three reaches integers from three onward. Both the base case and a valid step for every subsequent index are required.

02 / WORKED EXAMPLES

See the method in action.

EXAMPLE 01

A sum of odd numbers

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

Worked solution

1
Verify the base case.
$n = 1 : 1 = 1^{2}$
The statement is true at the first index in the domain.
2
State the hypothesis at an arbitrary k.
$1 + 3 + \dots + (2 k - 1) = k^{2}, k \geq 1$
Assume the assertion only for this one arbitrary integer.
3
Add the next odd number and simplify.
$\begin{aligned} 1 + 3 + \dots + (2 k - 1) + (2 k + 1) & = k^{2} + 2 k + 1 \\ = {(k + 1)}^{2} \end{aligned}$
The new term is $2 (k + 1) - 1 = 2 k + 1$ ; the hypothesis replaces the first k terms.
4
Conclude by induction.
$1 + 3 + \dots + (2 n - 1) = n^{2} (n \in ℤ, n \geq 1)$
The base and the implication together establish every positive integer case.

Answer

True for all integers $n \geq 1$ .

EXAMPLE 02

A recurrence identity

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

Worked solution

1
Verify the initial term.
$u_{1} = 3 = 2 (1) + 1$
The proposed explicit formula matches the given starting value.
2
Assume the formula at an arbitrary index.
$u_{k} = 2 k + 1, k \geq 1$
This is the induction hypothesis, with k fixed but arbitrary.
3
Apply the recurrence to derive the next case.
$\begin{aligned} u_{k + 1} & = u_{k} + 2 \\ = (2 k + 1) + 2 \\ = 2 (k + 1) + 1 \end{aligned}$
The given recurrence and the k hypothesis yield the required formula at k plus one.
4
Conclude the permitted domain.
$u_{n} = 2 n + 1 (n \in ℤ, n \geq 1)$
Induction propagates the verified initial case to every later index.

Answer

True for all integers $n \geq 1$ .

03 / YOUR TURN

Try it yourself.

Check your understanding

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

Show answer & reasoning

All integers $n \geq 2$ .

The verified starting case is two. The implication then establishes three, four and every later integer, so precisely all integers $n \geq 2$ are covered.

Keep practising

6 worksheet questions · 16 marks

Open worksheet Worked solutions

Read the questions online

Check the base case for $1 + 2 + \dots + n = \frac{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 = \frac{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 = \frac{n (n + 1)}{2}$ .
2 marks
The two sides agree for the first permitted integer.
At $n = 1$ , $1 = \frac{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 = \frac{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.
$\frac{k (k + 1)}{2} + (k + 1) = \frac{(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 = \frac{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…

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 ↗

In this lesson

Understand the idea.

Start a chain, then prove every link

Show the algebra that makes the next case

See the method in action.

A sum of odd numbers

Verify the base case.

State the hypothesis at an arbitrary k.

Add the next odd number and simplify.

Conclude by induction.

A recurrence identity

Verify the initial term.

Assume the formula at an arbitrary index.

Apply the recurrence to derive the next case.

Conclude the permitted domain.

Try it yourself.

Check your understanding

Keep practising