Mathematical induction for general statements: recurrence relations and properties

Syllabus dot point

“Apply mathematical induction to prove general statements about a recursive sequence, a property of a formula, or a recursive procedure”

HSCMaths Extension 1Proof (ME-P1)11 min readUpdated 20 Jun 2026

Quick answer

Induction proves closed-form formulas for recurrences and property-preservation statements with the same four-part structure as series and divisibility; the inductive step runs the recurrence or the iteration one stage, substitutes the hypothesis, and lands on the $n = k + 1$ case, finishing with the principle of mathematical induction. Use strong induction (with extra base cases) only when the step reaches back more than one term.

Jump to a section

What this dot point is asking
The answer
Exam-style questions

What this dot point is asking

NESA wants you to apply induction to statements that do not fall into the three tidy categories of sums, divisibility or inequalities. The two most common are a closed-form formula for a recursively defined sequence (you are given the rule that makes each term from the previous one, and asked to prove a single formula for the $n$ -th term) and a property preserved by a process (some feature is true at each stage of an iteration). The four-part structure is unchanged; what changes is the engine of the step, which is now the recurrence or the iteration rule rather than algebraic simplification.

The answer

Closed form for a recurrence

A closed form for a recurrence is a direct formula $a_n = g(n)$ that gives the $n$ -th term without computing all the earlier ones. You are typically given a starting value $a_1 = c$ and a rule $a_{n + 1} = f(a_n)$ , and asked to prove the formula $a_n = g(n)$ holds for all $n$ . The strategy:

Base case: check $g(1) = c$ , that is, the formula reproduces the given first term.
Hypothesis: assume $a_k = g(k)$ .
Step: apply the recurrence and substitute the hypothesis: $a_{k + 1} = f(a_k) = f\big(g(k)\big)$ , then simplify and show this equals $g(k + 1)$ .
Conclusion: by the principle of mathematical induction, $a_n = g(n)$ for all positive integers $n$ .

The decisive move in the step is to feed the recurrence its input from the hypothesis. The recurrence tells you how to get $a_{k + 1}$ from $a_k$ ; the hypothesis tells you what $a_k$ is; together they pin down $a_{k + 1}$ , and your job is to show the result is $g(k + 1)$ .

Key fact

For a recurrence proof, the recurrence drives the step and the closed form is the target. Always start the step from $a_{k + 1} = f(a_k)$ (the rule), then substitute $a_k = g(k)$ (the hypothesis), and simplify to $g(k + 1)$ . Never start from the closed form for $a_{k + 1}$ , that would assume what you are proving.

Properties preserved by a process

A property preserved by a process is one that, once true at some stage, stays true at the next. Many questions describe an iteration (repeatedly applying an operation, building up a figure, running an algorithm) and ask you to prove some feature holds at every stage. The inductive step is a conditional claim: if the property holds after $k$ steps, it holds after $k + 1$ . You assume the property at stage $k$ , perform one more step of the process, and show the property survives. Counting results (how many subsets, how many regions, how many handshakes) usually fit this mould, with the step explaining what one more element adds.

Strong induction (rarely needed in HSC)

Strong induction is the variant where the step at $n = k + 1$ may rely on the statement at all earlier values, not just at $n = k$ . It is occasionally useful when a recurrence reaches back two terms, such as the Fibonacci rule $F_{n + 1} = F_n + F_{n - 1}$ , since the step then needs both $F_k$ and $F_{k - 1}$ . Standard induction is enough for almost all HSC Extension 1 questions. If you do need the stronger form, say so: state the hypothesis as "assume the statement holds for all integers up to $k$ " and verify enough base cases (two of them for a two-term recurrence) to get the chain started.

Choosing the induction variable

When a statement contains more than one integer that could grow, you induct on one of them and hold the others fixed. Pick the variable that the recurrence or the structure actually steps through. For a statement like " $\sum_{i = 1}^{n} f(i) = g(n)$ for all positive integers $n$ ", you induct on $n$ regardless of what $f$ is; the function $f$ is carried symbolically and never inducted on. Naming your induction variable explicitly avoids confusion in multi-letter problems.

How exam questions ask about general statements

"A sequence is defined by $a_1 = \dots$ and $a_{n + 1} = \dots$ . Prove that $a_n = \dots$ ": a closed-form recurrence proof. Use the recurrence in the step, the formula as the target.
"Prove that $a_n = \dots$ satisfies the recurrence": the reverse phrasing; you still induct, checking the formula reproduces the rule.
"A process is repeated $n$ times. Prove that after $n$ steps, [property] holds": a property-preservation proof. Assume the property at step $k$ , do one more step, show it persists.
"Prove that a set with $n$ elements has $2^n$ subsets" (or similar counting claims): a structural induction; the step explains what adding one element does.
"Prove the formula for $F_n$ / a two-term recurrence": a hint that you may need strong induction with two base cases.

Exam technique

Identify the recurrence and the target before you write anything, and keep them visually separate. Begin the step with the recurrence, " $a_{k + 1} = f(a_k)$ ", then on the next line substitute the hypothesis and say "by the inductive hypothesis", then simplify to $g(k + 1)$ and state that it matches the formula at $n = k + 1$ . For a two-term recurrence, verify two base cases ( $n = 1$ and $n = 2$ ) and declare you are using strong induction. For a counting or structural claim, describe in words what the $(k + 1)$ -th element adds, then count. End with the named conclusion sentence in every case.

Worked example

Prove a closed form for a linear recurrence

A sequence is defined by $a_1 = 3$ and $a_{n + 1} = 2 a_n - 1$ . Prove that $a_n = 2^n + 1$ for all positive integers $n$ .

Base case ( $n = 1$ ): The given first term is $a_1 = 3$ , and the formula gives $2^1 + 1 = 3$ . They match, so the formula holds for $n = 1$ .
Inductive hypothesis: Assume the formula holds for $n = k$ , that is $a_k = 2^k + 1$ .
Inductive step: Start from the recurrence and feed in the hypothesis:

a_{k + 1} = 2 a_k - 1 = 2(2^k + 1) - 1 = 2^{k + 1} + 2 - 1 = 2^{k + 1} + 1.

This is the closed form with $n = k + 1$ , so the formula holds for $n = k + 1$ .

Conclusion: Since the base case holds and $P(k) \implies P(k + 1)$ , by the principle of mathematical induction $a_n = 2^n + 1$ for all positive integers $n$ .

Prove a closed form for a non-linear recurrence

Suppose $a_1 = 1$ and $a_{n + 1} = \dfrac{a_n}{1 + a_n}$ . Prove that $a_n = \dfrac{1}{n}$ for all positive integers $n$ .

Base case ( $n = 1$ ): $a_1 = 1 = \frac{1}{1}$ . The formula holds.
Inductive hypothesis: Assume $a_k = \frac{1}{k}$ .
Inductive step: Apply the recurrence and substitute,

a_{k + 1} = \frac{a_k}{1 + a_k} = \frac{\tfrac{1}{k}}{1 + \tfrac{1}{k}} = \frac{\tfrac{1}{k}}{\tfrac{k + 1}{k}} = \frac{1}{k + 1}.

This is the formula with $n = k + 1$ .

Conclusion: By the principle of mathematical induction, $a_n = \frac{1}{n}$ for all positive integers $n$ .

Prove a set of $n$ elements has $2^n$ subsets

Prove that a set with $n$ elements has $2^n$ subsets, for all non-negative integers $n$ .

Base case ( $n = 0$ ): The empty set has exactly one subset, itself, and $2^0 = 1$ . The claim holds.
Inductive hypothesis: Assume every set with $k$ elements has $2^k$ subsets.
Inductive step: Take a set $S$ with $k + 1$ elements, and single out one element $x$ , so $S = T \cup \{x\}$ where $T$ has $k$ elements. Every subset of $S$ either contains $x$ or it does not. The subsets that do not contain $x$ are precisely the subsets of $T$ , and there are $2^k$ of them by the hypothesis. The subsets that do contain $x$ are formed by taking a subset of $T$ and adding $x$ , again $2^k$ of them. Hence $S$ has $2^k + 2^k = 2 \cdot 2^k = 2^{k + 1}$ subsets.
Conclusion: By the principle of mathematical induction, a set with $n$ elements has $2^n$ subsets for all non-negative integers $n$ .

Prove a Fibonacci sum identity

The Fibonacci sequence has $F_1 = F_2 = 1$ and $F_{n + 1} = F_n + F_{n - 1}$ for $n \ge 2$ . Prove that $\sum_{i = 1}^{n} F_i = F_{n + 2} - 1$ for all positive integers $n$ .

Base case ( $n = 1$ ): LHS $= F_1 = 1$ , RHS $= F_3 - 1 = 2 - 1 = 1$ . The identity holds. (Only one base case is needed here, because the step below reaches back just one term through the sum, not two.)
Inductive hypothesis: Assume $\sum_{i = 1}^{k} F_i = F_{k + 2} - 1$ .
Inductive step: Split off the last term and apply the hypothesis, then use the Fibonacci rule $F_{k + 2} + F_{k + 1} = F_{k + 3}$ ,

\sum_{i = 1}^{k + 1} F_i = \sum_{i = 1}^{k} F_i + F_{k + 1} = (F_{k + 2} - 1) + F_{k + 1} = F_{k + 3} - 1.

This is the formula with $n = k + 1$ .

Conclusion: By the principle of mathematical induction, $\sum_{i = 1}^{n} F_i = F_{n + 2} - 1$ for all positive integers $n$ .

Edge cases and what-ifs

A two-term recurrence genuinely needs two base cases. If your step uses both $a_k$ and $a_{k - 1}$ (true strong induction), verify $n = 1$ and $n = 2$ and state that you assume the result for all values up to $k$ . One base case is not enough to start a two-step reach-back.
The base case can be $n = 0$ . Counting and structural claims often start at $n = 0$ (the empty set, zero steps). Verify the base at $0$ and conclude "for all non-negative integers".
Recurrence given for $a_n$ in terms of $a_{n - 1}$ . This is the same as $a_{n + 1} = f(a_n)$ shifted by one; just be consistent about which index you call $k$ and which $k + 1$ .
A formula that satisfies the recurrence but a different first term. A closed form must match both the recurrence and the given initial value. Check the base case carefully; two formulas can satisfy the same recurrence yet differ in $a_1$ .

Common traps

Confusing the recurrence with the closed form: The recurrence $a_{n + 1} = 2 a_n - 1$ defines the sequence; the closed form $a_n = 2^n + 1$ is what you are proving. Use the recurrence in the step, never the closed form for $a_{k + 1}$ .
Skipping the base case: Even for non-standard statements the base must be verified, often just confirming the formula gives the stated $a_1$ . Write it explicitly.
Forgetting to cite the hypothesis: Markers want "by the inductive hypothesis" at the point where you substitute $a_k = g(k)$ .
Choosing the wrong induction variable: If two variables both grow, induct on the one the structure steps through and hold the other fixed.
Using strong induction without saying so: If the step uses $a_{k - 1}$ , the hypothesis must cover earlier terms and you need two base cases. State that you are using strong induction.

Exam-style questions

Questions in the style of NESA exam questions on this dot point, each with a worked answer. They are written by ExamExplained unless tagged "Past paper"; the year shows the paper a question is modelled on.

HSC-style3 marks

A sequence is defined by

a_1 = 2

and

a_{n + 1} = 3 a_n - 2

. Prove by mathematical induction that

a_n = 3^{n - 1} + 1

for all positive integers

n

Show worked answer →

Base ( $n = 1$ ): $a_1 = 2$ and the formula gives $3^0 + 1 = 1 + 1 = 2$ . True.

Hypothesis: assume $a_k = 3^{k - 1} + 1$ for some positive integer $k$ .

Step: using the recurrence, $a_{k + 1} = 3 a_k - 2 = 3(3^{k - 1} + 1) - 2 = 3^k + 3 - 2 = 3^k + 1$ .

This is the formula with $n = k + 1$ (since $3^{(k + 1) - 1} + 1 = 3^k + 1$ ).

Conclusion: by mathematical induction, $a_n = 3^{n - 1} + 1$ for all positive integers $n$ .

HSC-style3 marks

Prove by mathematical induction that

n^3 + 2 n

is divisible by

3

for all positive integers

n

Show worked answer →

Base ( $n = 1$ ): $1 + 2 = 3 = 3 \times 1$ , divisible by $3$ . True.

Hypothesis: assume $k^3 + 2 k = 3 M$ for some integer $M$ .

Step: $(k + 1)^3 + 2(k + 1) = k^3 + 3 k^2 + 3 k + 1 + 2 k + 2 = (k^3 + 2 k) + 3 k^2 + 3 k + 3$ .

$= 3 M + 3(k^2 + k + 1) = 3\left( M + k^2 + k + 1 \right)$ , which is divisible by $3$ .

Conclusion: by mathematical induction, $n^3 + 2 n$ is divisible by $3$ for all positive integers $n$ .

Practise this

Sources & how we know this

Mathematics Extension 1 Stage 6 Syllabus (2017) — NESA
Mathematics Extension 1 HSC exam papers — NESA