# IB DP Maths Topic 10.11 The first-degree linear recurrence relation un=aun−1+b . HL Paper 3

## Question

Andy and Roger are playing tennis with the rule that if one of them wins a game when serving then he carries on serving, and if he loses then the other player takes over the serve.

The probability Andy wins a game when serving is $$\frac{1}{2}$$ and the probability he wins a game when not serving is $$\frac{1}{4}$$. Andy serves in the first game. Let $${u_n}$$ denote the probability that Andy wins the $${n^{{\text{th}}}}$$ game.

State the value of $${u_1}$$.

[1]
a.

Show that $${u_n}$$ satisfies the recurrence relation

${u_n} = \frac{1}{4}{u_{n – 1}} + \frac{1}{4}.$

[4]
b.

Solve this recurrence relation to find the probability that Andy wins the $${n^{{\text{th}}}}$$ game.

[6]
c.

After they have played many games, Pat comes to watch. Use your answer from part (c) to estimate the probability that Andy will win the game they are playing when Pat arrives.

[2]
d.

## Markscheme

$$\frac{1}{2}$$     A1

[1 mark]

a.

Andy could win the $${n^{{\text{th}}}}$$ game by winning the $$n – {1^{{\text{th}}}}$$ and then winning the $${n^{{\text{th}}}}$$ game or by losing the $$n – {1^{{\text{th}}}}$$ and then winning the $${n^{{\text{th}}}}$$     (M1)

$${u_n} = \frac{1}{2}{u_{n – 1}} + \frac{1}{4}(1 – {u_{n – 1}})$$     A1A1M1

Note:     Award A1 for each term and M1 for addition of two probabilities.

$${u_n} = \frac{1}{4}{u_{n – 1}} + \frac{1}{4}$$     AG

[4 marks]

b.

general solution is $${u_n} = A{\left( {\frac{1}{4}} \right)^n} + p(n)$$     (M1)

for a particular solution try $$p(n) = b$$     (M1)

$$b = \frac{1}{4}b + \frac{1}{4}$$     (A1)

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

hence $${u_n} = A{\left( {\frac{1}{4}} \right)^n} + \frac{1}{3}$$     (A1)

using $${u_1} = \frac{1}{2}$$     M1

$$\frac{1}{2} = A\left( {\frac{1}{4}} \right) + \frac{1}{3} \Rightarrow A = \frac{2}{3}$$

hence $${u_n} = \frac{2}{3}{\left( {\frac{1}{4}} \right)^n} + \frac{1}{3}$$     A1

Note:     Accept other valid methods.

[6 marks]

c.

for large $$n{\text{ }}{u_n} \approx \frac{1}{3}$$     (M1)A1

[2 marks]

Total [13 marks]

d.

## Examiners report

Not all candidates wrote this answer down correctly although it was essentially told you in the question.

a.

Very badly answered. Candidates seemed to think that they were being told this relationship (so used it to find u(2)) rather than attempting to prove it.

b.

This distinguished the better candidates. Some candidates though that they could use the method for homogeneous recurrence relations of second order and hence started solving a quadratic. Only the better candidates saw that it was a combined AP/GP.

c.

The best candidates saw this but most had not done enough earlier to get to do this.

d.

## 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$$.

[5]
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$$.

[7]
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}$$.

[4]
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}$$.

[1]
a.

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

[6]
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$$.

[6]
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.