Recognising incomplete or invalid induction arguments | Year 12

01 / LEARN

Understand the idea.

Check both obligations

An induction proof has two independent obligations: a true starting case and a valid successor implication. A flawless implication cannot start itself, and several true starting examples cannot replace the general implication.

Check which indices the step reaches. A step from $k$ to $k + 2$ keeps the parity of the index, so a base at one reaches odd indices only; a separate even base is needed for all positive integers.

Find the unjustified line

Trace the justification for each line. If the calculation uses the desired $P (k + 1)$ before deriving it, the reasoning is circular. Repair the missing bridge rather than checking more individual examples.

One counterexample in the claimed domain disproves a universal statement. An incomplete proof may still concern a true statement, so distinguish a false claim from a true claim whose proof lacks a base, a step or domain coverage.

02 / WORKED EXAMPLES

See the method in action.

EXAMPLE 01

A false starting case

A student claims $1 + 2 + \dots + n = n (n + 1) / 2 + 1$ and obtains plausible successor algebra. Why does the proof fail?

Worked solution

1
Test the required first case.
$\begin{aligned} left side at n = 1 & = 1, \\ right side at n = 1 & = \frac{1 \cdot 2}{2} + 1 = 2. \end{aligned}$
The claimed equality already fails at an allowed input.
2
Identify what the successor calculation preserves.
$(\frac{k (k + 1)}{2} + 1) + (k + 1) = \frac{(k + 1) (k + 2)}{2} + 1.$
Adding the next term preserves the extra one, so the conditional algebra can be valid even for a false claim.
3
Reject the claimed proof.
$1 \neq 2.$
There is no true base to begin the chain; the input $n = 1$ also directly refutes the universal statement.

Answer

The base case is false.

EXAMPLE 02

Missing even indices

P(1) is checked and P(k) implies P(k+2) is proved. What is missing?

Worked solution

1
Track the indices reached from the given base.
$P (1) \Rightarrow P (3) \Rightarrow P (5) \Rightarrow \dots$
A two-step implication preserves odd parity.
2
Identify the uncovered chain.
$P (2) \Rightarrow P (4) \Rightarrow P (6) \Rightarrow \dots$
No supplied base establishes the first even case.
3
State a sufficient repair.
$Verify P (2), or prove P (k) \Rightarrow P (k + 1) .$
A valid second base starts the even chain; a valid one-step implication from the original base reaches both parities.

Answer

A valid even base or a one-step implication.

03 / YOUR TURN

Try it yourself.

Check your understanding

How many allowed counterexamples refute a universal claim?

Show answer & reasoning

One.

A universal claim requires every allowed case to hold. One allowed input for which it fails is enough to refute the claim, regardless of how many other cases succeed.

Keep practising

6 worksheet questions · 15 marks

Open worksheet Worked solutions

Read the questions online

A student assumes the result at $k + 1$ and rearranges it to the hypothesis at $k$ . Explain the logical gap.
3 marks
Why do correct checks for the first one hundred positive integers not constitute induction?
2 marks
The step is proved only for $k$ at least 5 and the student checks $P (3)$ . What is missing to establish every $n$ at least 3?
3 marks
Refute the claim that $n^{2} + n + 41$ is prime for every positive integer $n$ .
3 marks
A sum of odd numbers proof adds $2 k - 1$ to the assumed total $k^{2}$ . Correct the next term.
2 marks
A divisibility proof concludes $A (k + 1) = d (q + \frac{1}{2})$ with integer $q$ . Explain the problem.
2 marks

Read the worked solutions

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

A student assumes the result at $k + 1$ and rearranges it to the hypothesis at $k$ . Explain the logical gap.
3 marks
Derive $P (k + 1)$ from $P (k)$ .
If reversing algebra, explicitly justify that each step is reversible.
The direction written is the reverse of the required implication.
Why do correct checks for the first one hundred positive integers not constitute induction?
2 marks
An untested case could still fail.
A starting case and a general successor implication are both required.
There is no implication proved for an arbitrary integer.
The step is proved only for $k$ at least 5 and the student checks $P (3)$ . What is missing to establish every $n$ at least 3?
3 marks
The implication cannot be used at $k = 3$ or $k = 4$ .
$P (5)$ is needed to start the valid chain.
$P (4)$ and $P (5)$ .
Refute the claim that $n^{2} + n + 41$ is prime for every positive integer $n$ .
3 marks
This allowed case is composite.
One counterexample refutes a universal claim.
$n = 41$ gives $41^{2} + 41 + 41 = 41 (43)$ .
A sum of odd numbers proof adds $2 k - 1$ to the assumed total $k^{2}$ . Correct the next term.
2 marks
The assumed sum already contains $2 k - 1$ .
The next odd number is $2 (k + 1) - 1$ .
It must add $2 k + 1$ .
A divisibility proof concludes $A (k + 1) = d (q + \frac{1}{2})$ with integer $q$ . Explain the problem.
2 marks
Integer divisibility requires an integer multiplier.
An arbitrary rational multiplier does not suffice.
The proposed multiplier is not an integer.

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 idea.

Check both obligations

Find the unjustified line

See the method in action.

A false starting case

Test the required first case.

Identify what the successor calculation preserves.

Reject the claimed proof.

Missing even indices

Track the indices reached from the given base.

Identify the uncovered chain.

State a sufficient repair.

Try it yourself.

Check your understanding

Keep practising