§-Syllabus dot point

NSWMaths Extension 1Syllabus dot point

How do we use induction to prove general statements involving a recursion, a formula or a property?

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

A focused answer to the HSC Maths Extension 1 dot point on induction for general statements beyond sums, divisibility and inequalities. Closed-form proofs for recursively defined sequences, properties preserved by an iterative process, a note on strong induction and choosing the induction variable, and worked linear and non-linear recurrences plus a counting result.

Generated by Claude Opus 4.811 min answerUpdated 2026-06-20

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

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)$ .

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.

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 practice questions

Practice questions written in the style of NESA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

HSC-style3 marksA 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 marksProve 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$ .