8.01g - Solving second-order recurrence relations | OCR A-Level Further Mathematics A

Solve second-order linear recurrence systems with constant coefficients using auxiliary equations, complementary functions and particular solutions. You will handle distinct real, repeated and complex roots, polynomial and exponential forcing, and the two initial conditions that select one sequence.

Two distinct real auxiliary roots

A sequence starts $u_0=1, u_1=1$ and obeys $u_{n+2}=u_{n+1}-u_n$ . Its next terms are $0,-1,-1,0,1,1$ . Why does this rule produce a six-term cycle rather than growing Fibonacci numbers? Its auxiliary roots, although complex, will describe a completely real sequence.

Begin with real roots. A second-order relation uses two preceding terms, so two initial conditions are generally needed. Its general solution has two arbitrary constants.

You already know

For a first-order linear relation, substitute an exponential trial to obtain an auxiliary equation, then add a particular solution if there is forcing. Euler's formula gives $e^{i\theta}=\cos\theta+i\sin\theta$ , and conjugate exponentials combine into real sine and cosine expressions.

Substitution of $u_n=\lambda^n$ into $u_{n+2}-au_{n+1}-bu_n=0$ gives

\lambda^{n+2}-a\lambda^{n+1}-b\lambda^n=0 \quad\Rightarrow\quad \lambda^2-a\lambda-b=0

for non-zero $\lambda$ . Each root supplies an exponential solution.

Distinct real auxiliary roots

For a homogeneous second-order relation with distinct non-zero real auxiliary roots $r$ and $s$ , the complementary function is

u_n=Ar^n+Bs^n

Two initial conditions determine $A$ and $B$ .
Not in the formula booklet: learn it.

The coefficient of $u_n$ has the opposite sign in the auxiliary polynomial when the recurrence is written with $u_{n+2}$ alone on the left. Move all terms to one side before forming the equation.

Worked example 1: two positive roots

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

Plan. Factor the auxiliary equation, then solve the two equations from the initial values.

\begin{aligned} \lambda^2-4\lambda+3&=(\lambda-3)(\lambda-1)=0 && \text{auxiliary equation} \\ u_n&=A3^n+B && \text{complementary function} \\ A+B&=2,\qquad 3A+B=4 && n=0,1 \\ A&=1,\qquad B=1 && \text{subtract the equations} \end{aligned}

Why this step? Both exponential solutions are required before imposing the two independent starting values.

Answer. $u_n=3^n+1$ .

Check. $u_2=10=4(4)-3(2)$ .

The next example changes the second root from $1$ to $-1$ , keeping the initial values. One component now alternates.

Worked example 2: one negative root

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

Plan. Retain the negative auxiliary root in its exponential term and apply both conditions.

\begin{aligned} \lambda^2-2\lambda-3&=(\lambda-3)(\lambda+1)=0 && \text{factorise} \\ v_n&=A3^n+B(-1)^n && \text{complementary function} \\ A+B&=2,\qquad 3A-B=4 && \text{initial conditions} \\ A&=\tfrac32,\qquad B=\tfrac12 && \text{solve simultaneously} \end{aligned}

Why this step? Replacing $(-1)^n$ by $-1$ would remove the second exponential solution and fail after the first term.

Answer. $v_n=\frac32 3^n+\frac12(-1)^n$ .

Check. $v_2=14=2(4)+3(2)$ .

If the coefficient of $u_n$ is zero, the auxiliary equation has a zero root: solve the resulting first-order relation for $u_{n+1}$ , keeping $u_0$ separately. For example, $u_{n+2}=2u_{n+1}$ gives $u_n=u_1 2^{n-1}$ for $n\ge1$ . This avoids ambiguous expressions involving $0^0$ .

Watch out

Wrong: $u_{n+2}=2u_{n+1}+3u_n$ gives $\lambda^2-2\lambda+3=0$ . Right: move both right-hand terms left, giving $\lambda^2-2\lambda-3=0$ .

The next relation changes the positive root while keeping the alternating root.

A repeated auxiliary root

A repeated root cannot supply two different exponential terms. Writing $Ar^n+Br^n$ merely combines into one constant times $r^n$ , so a second form is needed.

For a repeated non-zero root $r$ , the relation is

u_{n+2}-2ru_{n+1}+r^2u_n=0

Substitution shows that $nr^n$ satisfies it too: its left side is $r^{n+2}[(n+2)-2(n+1)+n]=0$ .

A repeated auxiliary root

If $r\ne0$ is a repeated root of the auxiliary equation, the complementary function is

u_n=(A+Bn)r^n

Not in the formula booklet: learn it.

The factor $n$ supplies the second independent solution. It plays the same role as the factor $x$ for a repeated auxiliary root in a second-order differential equation.

Worked example 3: a repeated positive root

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

Plan. Identify the repeated root, use the repeated-root form, then apply both conditions.

\begin{aligned} \lambda^2-4\lambda+4&=(\lambda-2)^2=0 && \text{repeated root } 2 \\ u_n&=(A+Bn)2^n && \text{complementary function} \\ A&=3,\qquad 2(A+B)=8 && \text{initial conditions} \\ B&=1 && \text{substitute } A=3 \end{aligned}

Why this step? Two constants multiplying the same $2^n$ would collapse; the extra factor $n$ allows two starting conditions to be met.

Answer. $u_n=(3+n)2^n$ .

Check. $u_2=20=4(8)-4(3)$ .

The next example changes only the sign of the repeated root. The bracket still advances linearly, but the exponential now changes sign.

Worked example 4: a repeated negative root

Question. Solve $v_{n+2}+4v_{n+1}+4v_n=0$ , $n\ge0$ , given $v_0=3, v_1=8$ .

Plan. Use $(A+Bn)(-2)^n$ , taking care at $n=1$ .

\begin{aligned} \lambda^2+4\lambda+4&=(\lambda+2)^2=0 && \text{repeated root } -2 \\ v_n&=(A+Bn)(-2)^n && \text{complementary function} \\ A&=3,\qquad -2(A+B)=8 && \text{initial conditions} \\ B&=-7 && \text{solve the second equation} \end{aligned}

Why this step? The factor outside the bracket at $n=1$ is $-2$ , so it changes the equation for $B$ .

Answer. $v_n=(3-7n)(-2)^n$ .

Check. $v_2=-44=-4(8)-4(3)$ .

If the auxiliary polynomial is $\lambda^2$ , the recurrence is simply $u_{n+2}=0$ : retain the two supplied starting terms, and every later term is zero. Treating this directly is clearer than a repeated-zero-root power formula.

Watch out

Wrong: for a repeated root $2$ , write $A2^n+B2^n$ . Right: use $(A+Bn)2^n$ . Combining equal exponentials cannot provide a second adjustable term.

A repeated root can also make a sequence converge when its magnitude is less than $1$ : the linear factor does not prevent $nr^n\to0$ for $|r|<1$ . This limit is not in the formula booklet: learn it.

Complex roots and real sequences

Complex auxiliary roots are tools for describing real oscillations. Write each conjugate root in modulus-argument form before raising it to the index.

If the roots are $re^{i\theta}$ and $re^{-i\theta}$ , Euler's formula combines their powers into real sine and cosine terms. Their common modulus $r$ controls the scale; their arguments control the oscillation.

Complex conjugate auxiliary roots

For roots $r(\cos\theta\pm i\sin\theta)$ , where $r>0$ , a real complementary function is

u_n=r^n\left(A\cos(n\theta)+B\sin(n\theta)\right)

with real constants $A,B$ .
De Moivre's theorem, used to raise the roots to powers, is in the formula booklet.
Not in the formula booklet: learn it.

For $r=1$ , suitable rational multiples of $\pi$ give periodic sequences. If $r<1$ , the bounded sine and cosine factors are multiplied by a power tending to zero.

Worked example 5: roots one plus or minus i

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

Plan. Convert the roots to modulus-argument form, then use the real complementary function.

\begin{aligned} \lambda&=1\pm i=\sqrt2\left(\cos\tfrac\pi4\pm i\sin\tfrac\pi4\right) && \text{solve the quadratic} \\ u_n&=(\sqrt2)^n\left(A\cos\tfrac{n\pi}4+B\sin\tfrac{n\pi}4\right) && \text{real complementary function} \\ A&=1,\qquad A+B=2 && \text{initial values at } 0,1 \\ B&=1 && \text{solve} \end{aligned}

Why this step? A conjugate pair of exponentials gives real sine and cosine components, so the final sequence can be written entirely with real numbers.

Answer. $u_n=(\sqrt2)^n(\cos\frac{n\pi}4+\sin\frac{n\pi}4)$ .

Check. The formula gives $u_2=2$ ; the recurrence gives $2(2)-2(1)=2$ .

The next example changes only the imaginary part of the roots. That changes both their modulus and their argument, so recalculate both.

Worked example 6: a different angle of oscillation

Question. Solve $v_{n+2}-2v_{n+1}+4v_n=0$ , $n\ge0$ , given $v_0=1, v_1=2$ .

Plan. Express $1\pm\sqrt3\,i$ in modulus-argument form and apply the initial conditions.

\begin{aligned} \lambda&=1\pm\sqrt3\,i=2\left(\cos\tfrac\pi3\pm i\sin\tfrac\pi3\right) && \text{modulus } 2 \\ v_n&=2^n\left(A\cos\tfrac{n\pi}3+B\sin\tfrac{n\pi}3\right) && \text{complementary function} \\ A&=1,\qquad A+\sqrt3 B=2 && n=0,1 \\ B&=\tfrac1{\sqrt3} && \text{solve} \end{aligned}

Why this step? The imaginary part $\sqrt3$ is not the argument; the root's angle is $\pi/3$ .

Answer. $v_n=2^n(\cos\frac{n\pi}3+\frac1{\sqrt3}\sin\frac{n\pi}3)$ .

Check. The formula gives $v_2=0$ ; the recurrence gives $2(2)-4(1)=0$ .

For the opening system, the auxiliary roots are $e^{\pm i\pi/3}$ , giving

u_n=\cos\frac{n\pi}3+\frac1{\sqrt3}\sin\frac{n\pi}3

Both trigonometric factors repeat when $n$ increases by $6$ , explaining the six-term cycle. Its terms are integers because the recurrence starts with integers and only subtracts them; the trigonometric form explains the repetition.

[DIAGRAM: asset_name: A recurrence with a six-term cycle; asset_slug: h245_8_01_six_term_cycle; caption: The roots have modulus one and arguments plus or minus pi over three, producing the repeating values 1, 1, 0, -1, -1, 0; description: Left panel shows the two auxiliary roots one half plus or minus square root of three over two times i on the unit circle at angles plus or minus pi over three. Right panel plots discrete terms for n from zero to eighteen, with braces identifying three repeats of the six-term cycle.]
The roots have modulus one and arguments plus or minus pi over three, producing the repeating values 1, 1, 0, -1, -1, 0

The cycle shows why complex roots need not mean complex answers.

Watch out

Wrong: roots $1\pm i$ give $A\cos n+B\sin n$ . Right: first find modulus $\sqrt2$ and argument $\pi/4$ , then include both $(\sqrt2)^n$ and $n\pi/4$ .

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.01g - Solving second-order recurrence relations

Two distinct real auxiliary roots

A repeated auxiliary root

Complex roots and real sequences

Continue this lesson.

Learn faster with Nova