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

A second-order recurrence relation links three consecutive terms: $u_{n+2}+f(n)u_{n+1}+g(n)u_n=h(n)$. Two starting values, usually $u_1$ and $u_2$, are needed to define the sequence. For $u_{n+2}=5u_{n+1}-6u_n$ with $u_1=1$ and $u_2=5$, the next terms are $u_3=5(5)-6(1)=19$ and $u_4=5(19)-6(5)=65$. When the right-hand side $h(n)$ is zero the relation is homogeneous; otherwise it is non-homogeneous. A closed form gives $u_n$ in terms of $n$ alone. The method extends the first-order method: general solution $=$ complementary function $+$ particular solution.

For the homogeneous relation $au_{n+2}+bu_{n+1}+cu_n=0$, try $u_n=m^n$. This gives the auxiliary equation $am^2+bm+c=0$. There are three cases.

• Two distinct real roots $m_1,m_2$: CF $=A\,m_1^n+B\,m_2^n$.
• A repeated root $m$: CF $=(A+Bn)m^n$.
• Complex roots: the CF involves $r^n$ multiplied by sines and cosines of $n\theta$ (it oscillates). Example: $2u_{n+2}+7u_{n+1}-15u_n=0$ has auxiliary equation $2m^2+7m-15=0$, which factorises as $(2m-3)(m+5)=0$, so $m=\frac32$ or $m=-5$ and the CF is $A\left(\frac32\right)^n+B(-5)^n$.

A particular solution satisfies the full relation. Choose a trial form to match $h(n)$: a constant $\lambda$ for constant $h$; $an+b$ for linear $h$; $an^2+bn+c$ for quadratic $h$; $\lambda r^n$ for $h(n)=kr^n$. Substitute and equate coefficients. Example: in $2u_{n+2}+7u_{n+1}-15u_n=6$ try $u_n=\lambda$: $2\lambda+7\lambda-15\lambda=6$, so $-6\lambda=6$ and $\lambda=-1$. Example: in $u_{n+2}-5u_{n+1}+6u_n=2n+1$ try $an+b$: $2an-3a+2b=2n+1$, so $a=1$, $b=2$. If the trial form already appears in the complementary function (for example a constant when $m=1$ is a root), multiply it by $n$.

Add the CF and PS, then use both initial conditions. Worked example: $2u_{n+2}+7u_{n+1}-15u_n=6$, $u_1=10$, $u_2=-17$. CF: $A\left(\frac32\right)^n+B(-5)^n$. PS: $-1$. General solution $u_n=A\left(\frac32\right)^n+B(-5)^n-1$. From $u_1=10$: $\frac32A-5B=11$. From $u_2=-17$: $\frac94A+25B=-16$. Solving gives $B=-1$ and $A=4$. So $u_n=4\left(\frac32\right)^n-(-5)^n-1.$ Check: $u_1=6+5-1=10$ and $u_2=9-25-1=-17$. Substitute the conditions into the full general solution, including the particular solution.

A second-order relation links $u_{k+2}$ to $u_{k+1}$ and $u_k$, so the induction needs two base cases and two assumed terms. Basis: check $n=1$ and $n=2$. Assumption: assume true for $n=k$ and $n=k+1$. Step: write $u_{k+2}$ using the recurrence, substitute both assumed forms and show the result is the formula with $n=k+2$. Conclusion: true for $n=1,2$, and true for $k,k+1$ implies true for $k+2$, so true for all positive integers $n$. Example: $u_{n+2}=3u_{n+1}-2u_n$, $u_1=1$, $u_2=3$, claim $u_n=2^n-1$. Basis: $2-1=1$, $4-1=3$. Step: $u_{k+2}=3(2^{k+1}-1)-2(2^k-1)=6\times2^k-3-2\times2^k+2=4\times2^k-1=2^{k+2}-1$.

The closed form shows long-term behaviour. For $u_n=3^n-2^n$ the root with the largest modulus, $3$, dominates, so $\frac{u_{n+1}}{u_n}\to3$. A root of modulus greater than 1 makes the sequence grow; a root of modulus less than 1 makes that part decay; a negative root makes that part alternate in sign, like $(-5)^n$. A repeated root gives the extra factor $n$, so growth is faster than for a single root. Always check a closed form by generating $u_3$ from the recurrence and comparing it with the formula.