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

What this dot point is asking

NESA wants you to use induction to prove statements that do not fall into the three standard categories (sums, divisibility, inequalities). The most common are closed-form formulas for recursively defined sequences and properties preserved by an iterative process.

The answer

Closed form for a recurrence

Suppose $a_1 = c$ and $a_{n + 1} = f(a_n)$. A typical question asks you to prove a closed-form formula $a_n = g(n)$ by induction.

Strategy:

1. Base case: Verify $g(1) = c$.
2. Hypothesis: Assume $a_k = g(k)$.
3. Step: Use the recurrence: $a_{k + 1} = f(a_k) = f(g(k))$. Show $f(g(k)) = g(k + 1)$.
4. Conclusion: By induction, $a_n = g(n)$ for all positive integers $n$.

Properties preserved by a process

Often a problem describes a process or iteration and asks you to prove some property is preserved. The induction step shows that if the property holds at iteration $k$, it holds at iteration $k + 1$.

Strong induction (rarely needed in HSC)

For some problems, the step at $n = k + 1$ needs not just the hypothesis at $n = k$ but at all $n \le k$. This is strong induction. It is rare in HSC Extension 1; standard induction is usually enough. If you find you need it, state the hypothesis as "assume the statement holds for all $n \le k$" and use any earlier instance you need.

Multi-variable extensions

Some statements have a parameter and an additional integer variable. You can induct on either, holding the other fixed.

For example, "prove that $\sum_{i = 1}^{n} f(i) = g(n)$ for all positive integers $n$" inducts on $n$ regardless of $f$. The proof handles $f$ symbolically.