Recurrence, Limits & Iteration

Recursive sequences in the HSC

A recursive sequence defines each term from previous ones: $x_{n+1}=f(x_n)$. Two big exam themes:

1. Financial maths — interest then repayment produces a linear recurrence solved by a finite GP.
2. Limits of recursion — assume $x_n\to L$, solve $L=f(L)$, then prove the limit rigorously.

Plain convergence theorems (monotone + bounded, algebra of limits, squeeze theorem) still apply when the sequence is given explicitly; recursion adds the fixed-point step.

Worked example 1 — Reducing-balance loan

A loan of $L$ grows by factor $(1+r)$ each period, then a repayment $P$ is subtracted. If $M_n$ is the balance after $n$ periods:

$$M_1=L(1+r)-P,$$

and unfolding yields

$$M_n=L(1+r)^n-P\sum_{k=0}^{n-1}(1+r)^k.$$

The sum is a finite GP with first term $1$ and ratio $1+r$:

$$M_n=L(1+r)^n-\frac{P\bigl((1+r)^n-1\bigr)}{r}\quad (r\neq 0).$$

Car loan: $L=20000$, $r=0.01$, $n=24$, set $M_{24}=0$ and solve for $P$:

$$P=\frac{Lr(1+r)^n}{(1+r)^n-1}.$$

Substitute the numbers carefully (calculator ok in exams when allowed).

Worked example 2 — Fixed point and contraction

Let $x_1=16$ and $x_{n+1}=2+\dfrac{1}{x_n}$.

If $x_n\to L>0$, then $L=2+\frac{1}{L}$, so $L^2-2L-1=0$ and $L=1+\sqrt{2}$ (positive root).

Error identity:

$$|x_{n+1}-L|=\frac{|x_n-L|}{L x_n}.$$

For $n\ge 2$ one can show $|x_{n+1}-L|<\frac14|x_n-L|$, hence the error shrinks geometrically and $x_n\to 1+\sqrt{2}$.

Method: candidate limit → error relation → geometric bound → convergence.

Worked example 3 — Iteration intuition

Plotting $y=f(x)$ and $y=x$, the recursion $x_{n+1}=f(x_n)$ is a cobweb: vertical to the curve, horizontal to the line $y=x$. Attracting fixed points pull the cobweb in; repelling points push it away. You rarely need a full diagram in Ext 1, but the picture explains why $|f'(L)|<1$ suggests local attraction.

For explicit sequences such as averages of squares over $n^3+k$, prefer inequalities and the squeeze theorem rather than recursion.

Common mistakes

• Solving $L=f(L)$ but never proving $x_n$ actually converges.
• In loans: subtracting $P$ before multiplying by $(1+r)$ when the question says interest is added first.
• Using $S_\infty$ formulae on a finite annuity sum.
• Sign errors when $r$ is a percentage vs a decimal ($1\%$ is $r=0.01$).

Practice (hints only)

1. Write $M_3$ from the loan recurrence and match it to the closed form.
2. For $x_{n+1}=\sqrt{2+x_n}$ with a suitable $x_1$, find $L$ and outline a monotone-bounded proof.

Where next

Advanced booklet topics connect recursion to special polynomials and generating functions: Chebyshev, Fibonacci, and generating functions.