First-order recurrence relationsEdexcel A-Level Further Maths: Revision notes

A recurrence relation defines each term of a sequence from earlier terms. A first-order relation involves only consecutive terms and has the form $u_{n+1}+f(n)u_n=g(n)$, where $f$ and $g$ are functions of $n$ (often constants). With a starting value such as $u_1$, you can generate terms one at a time: for $u_{n+1}-5u_n=8$ with $u_1=1$, $u_2=5(1)+8=13$ and $u_3=5(13)+8=73$. Recurrence relations model situations where a quantity changes in steps, such as a population that grows by a fixed percentage and is then reduced by a fixed number each year: $P_{n+1}=1.15P_n-60$. A closed form gives $u_n$ directly in terms of $n$, so that you can find any term without working through all the earlier ones.

Solving $u_{n+1}+fu_n=g(n)$ with constant $f$ has two parts. First solve the homogeneous relation $u_{n+1}+fu_n=0$ (right-hand side replaced by zero). Try $u_n=Am^n$, which gives the auxiliary equation $m+f=0$, so $m=-f$. The complementary function (CF) is $u_n=A(-f)^n$. For $u_{n+1}-5u_n=8$ the auxiliary equation is $m-5=0$, so the CF is $A\times5^n$, where $A$ is an arbitrary constant. The CF alone does not satisfy the full relation unless $g(n)=0$; it is the part that carries the arbitrary constant.

A particular solution (PS) is any single solution of the full relation $u_{n+1}+fu_n=g(n)$. Choose its form to match $g(n)$.

• $g(n)=k$ (constant): try $u_n=\lambda$.
• $g(n)$ linear, $pn+q$: try $u_n=an+b$.
• $g(n)$ quadratic: try $u_n=an^2+bn+c$.
• $g(n)=kr^n$: try $u_n=\lambda r^n$ (if $r$ is the root of the auxiliary equation, use $\lambda nr^n$). Substitute into the relation and compare coefficients. For $u_{n+1}-5u_n=8$, $u_n=\lambda$ gives $\lambda-5\lambda=8$, so $\lambda=-2$. For $u_{n+1}-2u_n=6n$, $u_n=an+b$ gives $-an+a-b=6n$, so $a=-6$, $b=-6$ and the PS is $-6n-6$.

The general solution is $u_n=\text{CF}+\text{PS}$. Use the starting value to find $A$. Worked example: $u_{n+1}-5u_n=8$, $u_1=1$. CF $=A\times5^n$ and PS $=-2$, so $u_n=A\times5^n-2$. When $n=1$: $5A-2=1$, so $A=\frac35$ and $u_n=\frac35\times5^n-2=3\times5^{n-1}-2.$ Check: $u_2=3(5)-2=13$, which matches $5(1)+8$. Always check against the first two terms generated directly from the recurrence. If the initial term is $u_0$ rather than $u_1$, substitute $n=0$.

To prove a closed form is correct, use induction. Basis: show the formula gives the right value for $n=1$. Assumption: assume $u_k$ equals the formula. Inductive step: use the recurrence to write $u_{k+1}$ in terms of $u_k$, substitute the assumed formula and show the result is the formula with $n=k+1$. Conclusion: a full sentence. Example: $u_{n+1}-3u_n=4$, $u_1=1$, prove $u_n=3^n-2$. For $n=1$: $3-2=1$. Assume $u_k=3^k-2$. Then $u_{k+1}=3u_k+4=3(3^k-2)+4=3^{k+1}-2$, which is the formula with $n=k+1$. True for $n=1$, and true for $k$ implies true for $k+1$, so true for all positive integers $n$ by mathematical induction.

In a model such as $P_{n+1}=1.15P_n-60$, the multiplier $1.15$ is the growth factor and $-60$ is a fixed removal each year. The constant particular solution $\lambda=1.15\lambda-60$ gives $\lambda=400$, which is the equilibrium value: if $P_n=400$ the population stays at 400. The closed form is $P_n=100(1.15)^{n-1}+400$ when $P_1=500$. Because the multiplier is greater than 1, the population grows without limit above 400 (and would fall below 400 if it started under it). Interpret the numbers in context and comment on limitations: real populations are not limited by a constant growth rate or exactly 60 removals.