Quick questions on Mathematical induction for general statements: recurrence relations and properties

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.

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

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.

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

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

Prove that for all positive integers $n$, $n^3 - n$ is divisible by $6$.

Suppose $a_1 = 1$ and $a_{n + 1} = \frac{a_n}{1 + a_n}$. Prove $a_n = \frac{1}{n}$.

Prove that an $n$-element set has $2^n$ subsets.

Even for non-standard statements, the base case must be verified. Often it is trivial (the formula matches the given $a_1$), but write it explicitly.

Markers want to see "by the hypothesis" or similar when you substitute $a_k = g(k)$.

If two variables both grow, induct on one and hold the other fixed.

If you use $a_{k - 1}$ in the step, the hypothesis must cover both $a_k$ and $a_{k - 1}$. :::