Question
(a) (i) Write down the general solution of the recurrence relation \({u_n} + 2{u_{n – 1}} = 0,{\text{ }}n \geqslant 1\).
(ii) Find a particular solution of the recurrence relation \({u_n} + 2{u_{n – 1}} = 3n – 2,{\text{ }}n \geqslant 1\), in the
form \({u_n} = An + B\), where \(A,{\text{ }}B \in \mathbb{Z}\).
(iii) Hence, find the solution to \({u_n} + 2{u_{n – 1}} = 3n – 2,{\text{ }}n \geqslant 1\) where \({u_1} = 7\).
(b) Find the solution of the recurrence relation \({u_n} = 2{u_{n – 1}} – 2{u_{n – 2}},{\text{ }}n \geqslant 2\), where \({u_0} = 2,{\text{ }}{u_1} = 2\). Express your solution in the form \({2^{f(n)}}\cos \left( {g(n)\pi } \right)\), where the functions f and g map \(\mathbb{N}\) to \(\mathbb{R}\).
▶️Answer/Explanation
Markscheme
(a) (i) use of auxiliary equation or recognition of a geometric sequence (M1)
\({u_n} = {( – 2)^n}{u_0}\) or \( = {\text{A}}{( – 2)^n}\) or \({u_1}{( – 2)^{n – 1}}\) A1
(ii) substitute suggested solution M1
\(An + B + 2\left( {A(n – 1) + B} \right) = 3n – 2\) A1
equate coefficients of powers of n and attempt to solve (M1)
\(A = 1,{\text{ }}B = 0\) A1
(so particular solution is \({u_n} = n\))
(iii) use of general solution = particular solution + homogeneous solution (M1)
\({u_n} = {\text{C}}{( – 2)^2} + n\) A1
attempt to find C using \({u_1} = 7\) M1
\({u_n} = – 3{( – 2)^n} + n\) A1
[10 marks]
(b) the auxiliary equation is \({r^2} – 2r + 2 = 0\) A1
solutions: \({r_1},{\text{ }}{r_2} = 1 \pm {\text{i}}\) A1
general solution of the recurrence: \({u_n} = {\text{A}}{(1 + {\text{i}})^n} + {\text{B}}{(1 – {\text{i}})^n}\) or trig form A1
attempt to impose initial conditions M1
\(A = B = 1\) or corresponding constants for trig form A1
\({u_n} = {2^{\left( {\frac{n}{2} + 1} \right)}} \times \cos \left( {\frac{{n\pi }}{4}} \right)\) A1A1
[7 marks]
Total [17 marks]
Examiners report
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]
Show that \({u_n}\) satisfies the recurrence relation
\[{u_n} = \frac{1}{4}{u_{n – 1}} + \frac{1}{4}.\][4]
Solve this recurrence relation to find the probability that Andy wins the \({n^{{\text{th}}}}\) game.[6]
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]
▶️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 M1 for addition of two probabilities.
\({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
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]
Question
Consider the recurrence relation
\({u_n} = 5{u_{n – 1}} – 6{u_{n – 2}},{\text{ }}{u_0} = 0\) and \({u_1} = 1\).
Find an expression for \({u_n}\) in terms of \(n\).[6]
For every prime number \(p > 3\), show that \(p|{u_{p – 1}}\).[4]
▶️Answer/Explanation
Markscheme
the auxiliary equation is \({\lambda ^2} – 5\lambda + 6 = 0\) M1
\( \Rightarrow \lambda = 2,{\text{ }}3\) (A1)
the general solution is \({u_n} = A \times {2^n} + B \times {3^n}\) A1
imposing initial conditions (substituting \(n = 0,{\text{ }}1\)) M1
\(A + B = 0\) and \(2A + 3B = 1\) A1
the solution is \(A = – 1,{\text{ }}B = 1\)
so that \({u_n} = {3^n} – {2^n}\) A1
[6 marks]
\({u_{p – 1}} = {3^{p – 1}} – {2^{p – 1}}\)
\(p > 3\), therefore 3 or 2 are not divisible by \(p\) R1
hence by FLT, \({3^{p – 1}} \equiv 1 \equiv {2^{p – 1}}(\bmod p)\) for \(p > 3\) M1A1
\({u_{p – 1}} \equiv 0(\bmod p)\) A1
\(p|{u_{p – 1}}\) for every prime number \(p > 3\) AG
[4 marks]
Examiners report
[N/A]
[N/A]
Question
Consider the recurrence relation
\({u_n} = 5{u_{n – 1}} – 6{u_{n – 2}},{\text{ }}{u_0} = 0\) and \({u_1} = 1\).
Find an expression for \({u_n}\) in terms of \(n\).[6]
For every prime number \(p > 3\), show that \(p|{u_{p – 1}}\).[4]
▶️Answer/Explanation
Markscheme
the auxiliary equation is \({\lambda ^2} – 5\lambda + 6 = 0\) M1
\( \Rightarrow \lambda = 2,{\text{ }}3\) (A1)
the general solution is \({u_n} = A \times {2^n} + B \times {3^n}\) A1
imposing initial conditions (substituting \(n = 0,{\text{ }}1\)) M1
\(A + B = 0\) and \(2A + 3B = 1\) A1
the solution is \(A = – 1,{\text{ }}B = 1\)
so that \({u_n} = {3^n} – {2^n}\) A1
[6 marks]
\({u_{p – 1}} = {3^{p – 1}} – {2^{p – 1}}\)
\(p > 3\), therefore 3 or 2 are not divisible by \(p\) R1
hence by FLT, \({3^{p – 1}} \equiv 1 \equiv {2^{p – 1}}(\bmod p)\) for \(p > 3\) M1A1
\({u_{p – 1}} \equiv 0(\bmod p)\) A1
\(p|{u_{p – 1}}\) for every prime number \(p > 3\) AG
[4 marks]
Examiners report
[N/A]
[N/A]
Question
The sequence \(\{ {u_n}\} \) , \(n \in {\mathbb{Z}^ + }\) , satisfies the recurrence relation \({u_{n + 2}} = 5{u_{n + 1}} – 6{u_n}\) .
Given that \({u_1} = {u_2} = 3\) , obtain an expression for \({u_n}\) in terms of n .[6]
The sequence \(\{ {v_n}\} \) , \(n \in {\mathbb{Z}^ + }\) , satisfies the recurrence relation \({v_{n + 2}} = 4{v_{n + 1}} – 4{v_n}\) .
Given that \({v_1} = 2\) and \({v_2} = 12\) , use the principle of strong mathematical induction to show that \({v_n} = {2^n}(2n – 1)\) .[8]
▶️Answer/Explanation
Markscheme
the auxiliary equation is
\({m^2} – 5m + 6 = 0\) M1
giving \(m = 2,{\text{ 3}}\) A1
the general solution is
\({u_n} = A \times {2^n} + B \times {3^n}\) A1
substituting n = 1, 2
\(2A + 3B = 3\) M1
\(4A + 9B = 3\) A1
the solution is A = 3, B = –1 giving \({u_n} = 3 \times {2^n} – {3^n}\) A1
[6 marks]
we first prove that \({v_n} = {2^n}(2n – 1)\) for n = 1, 2 M1
for n = 1, it gives \(2 \times 1 = 2\) which is correct
for n = 2 , it gives \(4 \times 3 = 12\) which is correct A1
we now assume that the result is true for \(n \leqslant k\) M1
consider
\({v_{k + 1}} = 4{v_k} – 4{v_{k – 1}}{\text{ }}(k \geqslant 2)\) M1
\( = {4.2^k}(2k – 1) – {4.2^{k – 1}}(2k – 3)\) A1
\( = {2^{k + 1}}(4k – 2 – 2k + 3)\) A1
\( = {2^{k + 1}}\left( {2(k + 1) – 1} \right)\) A1
this proves that if the result is true for \(n \leqslant k\) then it is true for \(n \leqslant k + 1\)
since we have also proved it true for \(n \leqslant 2\) , the general result is proved by induction R1
Note: A reasonable attempt has to be made to the induction step for the final R1 to be awarded.
[8 marks]
Examiners report
[N/A]
[N/A]