## 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}\).

Show that \({u_n}\) satisfies the recurrence relation

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

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

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.

**Answer/Explanation**

## Markscheme

\(\frac{1}{2}\) **A1**

**[1 mark]**

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

**for addition of two probabilities.**

*M1*\({u_n} = \frac{1}{4}{u_{n – 1}} + \frac{1}{4}\) *AG*

*[4 marks]*

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]**

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

*[2 marks]*

*Total [13 marks]*

## Examiners report

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

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.

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.

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

## 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\).

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\).

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}\).

**Answer/Explanation**

## 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]*

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]*

\({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]*

## 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}\).

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.

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.

## 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}\).

Find an expression for \({u_n}\) in terms of \(n\).

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\).

**Answer/Explanation**

## Markscheme

\({u_2} = – 9\) *A1*

*[1 mark]*

**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]*

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]**

## Examiners report

[N/A]

[N/A]

[N/A]