8.01f - Solving first-order recurrence relations | OCR A-Level Further Mathematics A

Solve first-order linear recurrence systems with constant coefficients, turning an update rule into a closed form. You will use an auxiliary equation and a complementary function, add a particular solution for polynomial or exponential forcing, and adapt a trial when it overlaps the complementary function.

The auxiliary equation and complementary function

A machine starts with $4$ units and updates its total by “double it, then add $3\times2^n$ ” on update $n$ . What is the total after $10$ updates, and why does a factor of $n$ appear in its closed form? The extra input grows by the same factor as the machine's existing total. That coincidence is the key to the final part.

Begin with no extra input. If $u_{n+1}=3u_n$ , each update triples every difference between two possible solutions. Exponential terms are therefore the natural building blocks.

You already know

A recurrence system includes an initial condition and an index range. A general solution contains an arbitrary constant; an initial condition selects one particular sequence. A power $a^n$ tends to $0$ when $|a|<1$ , including negative $a$ .

“Linear” means that the sequence terms occur only to the first power and are not multiplied together. Thus $u_{n+1}=2u_n+n^2$ is linear, but $u_{n+1}=u_n^2+1$ is not. “Constant coefficients” refers to the coefficients of the sequence terms, not the added function of $n$ .

Homogeneous relation and complementary function

For $u_{n+1}=au_n+f(n)$ , the associated homogeneous relation is $u_{n+1}=au_n$ . Its general solution is the complementary function. Substitution of $u_n=\lambda^n$ gives the auxiliary equation $\lambda-a=0$ . For $a\ne0$ , its solution is $u_n=Ca^n$ , with arbitrary constant $C$ .

The trial works because advancing $n$ multiplies $\lambda^n$ by $\lambda$ . The auxiliary equation and complementary-function result are not in the formula booklet: learn them.

Worked example 1: a positive auxiliary root

Question. Solve $u_{n+1}=3u_n$ for $n\ge0$ , given $u_0=2$ .

Plan. Find the auxiliary root, write the complementary function and apply the initial condition.

\begin{aligned} \lambda-3&=0\quad\Rightarrow\quad\lambda=3 && \text{auxiliary equation} \\ u_n&=C3^n && \text{complementary function} \\ 2&=C3^0\quad\Rightarrow\quad C=2 && u_0=2 \end{aligned}

Why this step? One initial condition fixes the single arbitrary constant in a first-order system.

Answer. $u_n=2\times3^n$ , for $n\ge0$ .

Check. $u_1=6=3u_0$ , and $u_{n+1}/u_n=3$ .

The next example changes only the sign of the multiplier. The auxiliary root carries that sign into every power.

Worked example 2: a negative auxiliary root

Question. Solve $v_{n+1}=-3v_n$ for $n\ge0$ , given $v_0=2$ .

Plan. Repeat the auxiliary-equation method, retaining the negative base.

\begin{aligned} \lambda+3&=0\quad\Rightarrow\quad\lambda=-3 && \text{auxiliary equation} \\ v_n&=C(-3)^n && \text{complementary function} \\ 2&=C(-3)^0\quad\Rightarrow\quad C=2 && v_0=2 \end{aligned}

Why this step? Writing $(-3)^n$ makes the sign alternate; $-3^n$ would stay negative.

Answer. $v_n=2(-3)^n$ , for $n\ge0$ .

Check. The first terms are $2,-6,18,-54$ , each obtained by multiplying by $-3$ .

If $a=0$ , handle the degenerate system directly: $u_{n+1}=f(n)$ , so $u_n=f(n-1)$ for $n\ge1$ , with $u_0$ supplied separately. There is no need to assign a value to $0^0$ .

Watch out

Wrong: use $C3^n$ for a multiplier of $-3$ . Right: the auxiliary root is $-3$ , giving $C(-3)^n$ . A sign lost in the complementary function changes every other term.

The next question varies the multiplier and the initial condition while keeping the same structure.

Polynomial particular solutions

An added function of $n$ requires one solution that matches that input, as well as the homogeneous part.

Suppose $p_n$ satisfies $p_{n+1}-ap_n=f(n)$ . If $u_n=p_n+Ca^n$ , substitution gives

u_{n+1}-au_n=(p_{n+1}-ap_n)+C(a^{n+1}-aa^n)=f(n)

Conversely, subtracting $p_n$ from any solution leaves a homogeneous solution. This explains why adding the two pieces gives the general solution.

Complementary function plus particular solution

For $a\ne0$ , a general solution of $u_{n+1}-au_n=f(n)$ is

u_n=Ca^n+p_n

where $p_n$ is any one particular solution. An initial condition fixes $C$ . The phrase “particular solution” here means one solution of the non-homogeneous relation; the final solution satisfying the initial condition is the particular solution of the full recurrence system.
Not in the formula booklet: learn it.

When $a\ne1$ and $f(n)$ is a polynomial of degree $m$ , try a polynomial of degree $m$ , including every lower power and the constant term. Substitution produces polynomial identities, so compare coefficients. For a constant input use a constant trial; for a linear input use $An+B$ ; for a quadratic input use $An^2+Bn+D$ . This trial rule is not in the formula booklet: learn it.

Worked example 3: a linear input

Question. Solve $u_{n+1}-2u_n=3n+1$ , $n\ge0$ , given $u_0=1$ .

Plan. Add a linear particular solution to the complementary function $C2^n$ .

Try $p_n=An+B$ . Then

\begin{aligned} p_{n+1}-2p_n&=A(n+1)+B-2(An+B) && \text{substitute the trial} \\ &=-An+(A-B)=3n+1 && \text{collect coefficients} \\ A&=-3,\qquad B=-4 && \text{compare powers of } n \end{aligned}

Thus

\begin{aligned} u_n&=C2^n-3n-4 && \text{add complementary function} \\ 1&=C-4\quad\Rightarrow\quad C=5 && \text{initial condition} \end{aligned}

Why this step? Even though the forcing is linear, its constant term and the index shift require both coefficients in the trial.

Answer. $u_n=5\times2^n-3n-4$ .

Check. $u_1=3$ ; the recurrence gives $2(1)+1=3$ . The trial itself satisfies $(-3(n+1)-4)-2(-3n-4)=3n+1$ .

The next example changes only the degree of the polynomial input. A quadratic trial needs its linear and constant terms even though the input has no linear term.

Worked example 4: a quadratic input

Question. Solve $v_{n+1}-2v_n=3n^2+1$ , $n\ge0$ , given $v_0=1$ .

Plan. Use $p_n=An^2+Bn+D$ , compare coefficients, then impose the initial condition.

\begin{aligned} p_{n+1}-2p_n&=-An^2+(2A-B)n+(A+B-D) && \text{expand the trial} \\ -A&=3,\quad 2A-B=0,\quad A+B-D=1 && \text{compare coefficients} \\ A&=-3,\quad B=-6,\quad D=-10 && \text{solve in order} \\ v_n&=C2^n-3n^2-6n-10 && \text{general solution} \\ 1&=C-10\quad\Rightarrow\quad C=11 && v_0=1 \end{aligned}

Why this step? Advancing a square generates a linear term; omitting $Bn$ would make it impossible to cancel that term.

Answer. $v_n=11\times2^n-3n^2-6n-10$ .

Check. $v_1=3$ , $v_2=10$ ; the updates give $2(1)+1=3$ , then $2(3)+4=10$ .

A higher-degree polynomial follows the same coefficient comparison. If several forcing terms are added, particular solutions can be added too, because the recurrence is linear.

Watch out

Wrong: for input $3n^2+1$ , try only $An^2+D$ . Right: include $Bn$ as well. Missing powers in the input do not imply missing powers in its particular solution.

A constant input is the shortest polynomial case: put $p_n=B$ into the relation and solve $(1-a)B=f(n)$ .

Exponential particular solutions

For an input $dk^n$ , use the same exponential base in the trial, provided it differs from the auxiliary root.

Substituting $p_n=Bk^n$ gives

p_{n+1}-ap_n=B(k-a)k^n

so the required coefficient is determined by $B(k-a)=d$ .

An exponential trial

For $u_{n+1}-au_n=dk^n$ , with $k\ne0$ and $k\ne a$ , a particular solution is

p_n=\frac{d}{k-a}k^n

Not in the formula booklet: learn the substitution.

If $k=a$ , the coefficient equation becomes $0=d$ , signalling that this trial has failed. The final part repairs it.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

8.01f - Solving first-order recurrence relations

The auxiliary equation and complementary function

Polynomial particular solutions

Exponential particular solutions

Continue this lesson.

Learn faster with Nova