# IB DP Maths Topic 10.11 Solution of first- and second-degree linear homogeneous recurrence relations with constant coefficients. HL Paper 3

## Question

The sequence $$\{ {u_n}\} ,{\text{ }}n \in \mathbb{N}$$, satisfies the recurrence relation $${u_{n + 1}} = 7{u_n} – 6$$.

Given that $${u_0} = 5$$, find an expression for $${u_n}$$ in terms of $$n$$.


a.

The sequence $$\{ {v_n}\} ,{\text{ }}n \in \mathbb{N}$$, satisfies the recurrence relation $${v_{n + 2}} = 10{v_{n + 1}} + 11{v_n}$$.

Given that $${v_0} = 4$$ and $${v_1} = 44$$, find an expression for $${v_n}$$ in terms of $$n$$.


b.

The sequence $$\{ {v_n}\} ,{\text{ }}n \in \mathbb{N}$$, satisfies the recurrence relation $${v_{n + 2}} = 10{v_{n + 1}} + 11{v_n}$$.

Show that $${v_n} – {u_n} \equiv 15(\bmod 16),{\text{ }}n \in \mathbb{N}$$.


c.

## Markscheme

METHOD 1

attempting to find a solution in the form $${u_n} = A{7^n} + B$$     M1

EITHER

eg, and $${u_0} = 5 \Rightarrow 5 = A + B{\text{ and }}{u_1} = 29 \Rightarrow 29 = 7A + B$$     A1

OR

$$A{7^{n + 1}} + B = A{7^{n + 1}} + 7B – 6\;\;\;$$(or equivalent)     A1

THEN

attempting to solve for $$A$$ and $$B$$     (M1)

$${u_n} = 4 \times {7^n} + 1$$     A1A1

Note:     Accept $$A = 4,{\text{ }}B = 1$$ provided the first M1 is awarded.

METHOD 2

attempting an iterative method eg, $${u_1} = 7{\text{(}}5) – 6$$ and

$${u_2} = {7^2}{\text{(}}5) – 6{\text{(}}7 + 1){\text{ }}(etc)$$     (M1)

$${u_n} = 5 \times {7^n} – 6\left( {\frac{{{7^n} – 1}}{{7 – 1}}} \right)$$     M1A1

Note:     Award M1 for attempting to express $${u_n}$$ in terms of $$n$$.

$${u_n} = 4 \times {7^n} + 1$$     A1A1

METHOD 3

attempting to find a solution in the form $${u_n} = A{7^n} + B$$     M1

$$A(n + 1) + B = 7(An + B) – 6$$

$$7B – 6 = B$$     A1

attempting to solve for $$A$$     (M1)

$${u_n} = 4 \times {7^n} + 1$$     A1A1

METHOD 4

$${u_{n + 1}} – 7{u_n} + 6 – ({u_n} – 7{u_{n + 1}} + 6) = 0 \Rightarrow {u_{n + 1}} – 8{u_n} + 7{u_{n – 1}} = 0$$

$${r^2} – 8r + 7 = 0$$

$$r = 1,{\text{ }}7$$

attempting to find a solution in the form $${u_n} = A{7^n} + B$$     M1

EITHER

eg, $${u_0} = 5 \Rightarrow 5 = A + B{\text{ and }}{u_1} = 29 \Rightarrow 29 = 7A + B$$     A1

OR

$$A{7^{n + 1}} + B = A{7^{n + 1}} + 7B – 6\;\;\;$$(or equivalent)     A1

THEN

attempting to solve for $$A$$ and $$B$$     (M1)

$${u_n} = 4 \times {7^n} + 1$$     A1A1

[5 marks]

a.

attempting to find the auxiliary equation     M1

$${r^2} – 10r – 11 = 0\;\;\;\left( {(r – 11)(r + 1) = 0} \right)$$     A1

$$r = 11,{\text{ }}r = – 1$$     A1

$${v_n} = A{11^n} + B{( – 1)^n}$$     (M1)

attempting to use the initial conditions     M1

$$A + B = 4,{\text{ }}11A – B = 44$$     A1

$${v_n} = 4 \times {11^n}$$     A1

[7 marks]

b.

$${v_n} – {u_n} = 4({11^n} – {7^n}) – 1$$     M1

EITHER

$$= 4(11 – 7)({11^{n – 1}} + \ldots + {7^{n – 1}}) – 1$$     M1A1

OR

$$= 4\left( {{{(7 + 4)}^n} – {7^n}} \right) – 1$$     A1

subtracting the $${7^n}$$ from the expanded first bracket     M1

THEN

obtaining $$16$$ times a whole number $$– 1$$     A1

$${v_n} – {u_n} \equiv 15(\bmod 16),{\text{ }}n \in \mathbb{N}$$     AG

[4 marks]

Total [16 marks]

c.

## Examiners report

In part (a), a good number of candidates were able to ‘see’ the solution form for $${u_n}$$ and then (often in non-standard ways) successfully obtain $${u_n} = 4 \times {7^n} + 1$$. A variety of methods and interesting approaches were seen here including use of the general closed form solution, iteration, substitution of $${u_n} = 4 \times {7^n} + 1$$, substitution of $${u_n} = An + B$$ and, interestingly, conversion to a second-degree linear recurrence relation. A number of candidates erroneously converted the recurrence relation to a quadratic auxiliary equation and obtained $${u_n} = {c_1}{(6)^n} + {c_2}{(1)^n}$$.

a.

Compared to similar recurrence relation questions set in recent examination papers, part (b) was reasonably well attempted with a substantial number of candidates correctly obtaining $${v_n} = 4{(11)^n}$$. It was pleasing to note the number of candidates who could set up the correct auxiliary equation and use the two given terms to obtain the required solution. It appeared that candidates were better prepared for solving second-order linear recurrence relations compared to first-order linear recurrence relations.

b.

Most candidates found part (c) challenging. Only a small number of candidates attempted to either factorise $${11^n} – {2^n}$$ or to subtract $${7^n}$$ from the expansion of $${(7 + 4)^n}$$. It was also surprising how few went for the option of stating that 11 and 7 are congruent $$\bmod 4$$ so $${11^n} – {7^n} \equiv (\bmod 4)$$ and hence is a multiple of 4.

c.

## Question

A recurrence relation is given by $${u_{n + 1}} + 2{u_n} + 1 = 0,{\text{ }}{u_1} = 4$$.

Use the recurrence relation to find $${u_2}$$.


a.

Find an expression for $${u_n}$$ in terms of $$n$$.


b.

A second recurrence relation, where $${v_1} = {u_1}$$ and $${v_2} = {u_2}$$, is given by $${v_{n + 1}} + 2{v_n} + {v_{n – 1}} = 0,{\text{ }}n \ge 2$$.

Find an expression for $${v_n}$$ in terms of $$n$$.


c.

## Markscheme

$${u_2} = – 9$$     A1

[1 mark]

a.

METHOD 1

$${u_{n + 1}} = – 2{u_n} – 1$$

let $${u_n} = a{( – 2)^n} + b$$     M1A1

EITHER

$$a{( – 2)^{n + 1}} + b = – 2\left( {a{{( – 2)}^n} + b} \right) – 1$$     M1

$$a{( – 2)^{n + 1}} + b = a{( – 2)^{n + 1}} – 2b – 1$$

$$3b = – 1$$

$$b = – \frac{1}{3}$$     A1

$${u_1} = 4 \Rightarrow – 2a – \frac{1}{3} = 4$$     (M1)

$$\Rightarrow a = – \frac{{13}}{6}$$     A1

OR

using $${u_1} = 4,{\text{ }}{u_2} = – 9$$

$$4 = – 2a + b,{\text{ }} – 9 = 4a + b$$     M1A1

solving simultaneously     M1

$$\Rightarrow a = – \frac{{13}}{6},{\text{ and }}b = – \frac{1}{3}$$     A1

THEN

so $${u_n} = – \frac{{13}}{6}{( – 2)^n} – \frac{1}{3}$$

METHOD 2

use of the formula $${u_n} = {a^n}{u_0} + b\left( {\frac{{1 – {a^n}}}{{1 – a}}} \right)$$     (M1)

letting $${u_0} = – \frac{5}{2}$$     A1

letting $$a = – 2$$ and $$b = – 1$$     A1

$${u_n} = – \frac{5}{2}{( – 2)^n} – 1\left( {\frac{{1 – {{( – 2)}^n}}}{{1 – – 2}}} \right)$$     M1A1

$$= – \frac{{13}}{6}{( – 2)^n} – \frac{1}{3}$$     A1

[6 marks]

b.

auxiliary equation is $${k^2} + 2k + 1 = 0$$     M1

hence $$k = – 1$$     (A1)

so let $${v_n} = (an + b){( – 1)^n}$$     M1

$$(2a + b){( – 1)^2} = – 9$$ and $$(a + b){( – 1)^1} = 4$$     A1

so $$a = – 5,{\text{ }}b = 1$$     M1A1

$${v_n} = (1 – 5n){( – 1)^n}$$

Note:     Caution necessary to allow FT from (a) to part (c).

[6 marks]

Total [13 marks]

c.

[N/A]

a.

[N/A]

b.

[N/A]

c.