Question
(a) Consider the recurrence relation \(a{u_{n + 1}} + b{u_n} + c{u_{n – 1}} = 0\).
Show that \({u_n} = A{\lambda ^n} + B{\mu ^n}\) satisfies this relation where \(A\), \(B\) are arbitrary constants and \(\lambda \), \(\mu \) are the roots of the equation \(a{x^2} + bx + c = 0\).
(b) 
A particle \(P\) executes a random walk on the line above such that when it is at point \(n\left( {1 \leqslant n \leqslant 9,{\text{ }}n \in {\mathbb{Z}^ + }} \right)\) it has a probability \(0.4\) of moving to \(n + 1\) and a probability \(0.6\) of moving to \(n – 1\). The walk terminates as soon as \(P\) reaches either \(0\) or \(10\). Let \({p_n}\) denote the probability that the walk terminates at \(0\) starting from \(n\).
(i) Show that \(2{p_{n + 1}} – 5{p_n} + 3{p_{n – 1}} = 0\).
(ii) By solving this recurrence relation subject to the boundary conditions \({p_0} = 1\), \({p_{10}} = 0\) show that \({p_n} = \frac{{{{1.5}^{10}} – {{1.5}^n}}}{{{{1.5}^{10}} – 1}}\).
Answer/Explanation
Markscheme
(a) consider
\(a{u_{n + 1}} + b{u_n} + c{u_{n – 1}} = aA{\lambda ^{n + 1}} + aB{\mu ^{n + 1}} + bA{\lambda ^n} + bB{\mu ^n} + cA{\lambda ^{n – 1}} + cB{\mu ^{n – 1}}\) M1A1
\( = A{\lambda ^{n – 1}}\left( {a{\lambda ^2} + b\lambda + c} \right) + B{\mu ^{n – 1}}\left( {a{\mu ^2} + b\mu + c} \right)\) A1
\(= 0 \)
[3 marks]
(b) (i) to terminate at \(0\) starting from \(n\), the particle must either move to \(n + 1\) and terminate at \(0\) starting from there or move to \(n – 1\) and terminate at \(0\) starting from there
therefore,
\({p_n} = 0.4{p_{n + 1}} + 0.6{p_{n – 1}}\) M1A2
leading to \(2{p_{n + 1}} – 5{p_n} + 3{p_{n – 1}} = 0\) AG
(ii) solving the auxiliary equation \(2{x^2} – 5x + 3 = 0\) M1
\(x = 1,{\text{ 1.5}}\) A1
the general solution is
\({p_n} = A + B{(1.5)^n}\) A1
substituting the boundary conditions,
\(A + B = 1\)
\(A + B{(1.5)^{10}} = 0\) M1A1
solving,
\(A = \frac{{{{1.5}^{10}}}}{{{{1.5}^{10}} – 1}};{\text{ }}B = – \frac{1}{{{{1.5}^{10}} – 1}}\) A1A1
giving
\({p_n} = \frac{{{{1.5}^{10}} – {{1.5}^n}}}{{{{1.5}^{10}} – 1}}\) AG
[10 marks]
Question
In 1985 , the deer population in a national park was \(330\). A year later it had increased to \(420\). To model these data the year 1985 was designated as year zero. The increase in deer population from year \(n – 1\) to year \(n\) is three times the increase from year \(n – 2\) to year \(n – 1\). The deer population in year \(n\) is denoted by \({x_n}\).
Show that for \(n \geqslant 2,{\text{ }}{x_n} = 4{x_{n – 1}} – 3{x_{n – 2}}\).
Solve the recurrence relation.
Show using proof by strong induction that the solution is correct.
Answer/Explanation
Markscheme
\({x_n} – {x_{n – 1}} = 3({x_{n – 1}} – {x_{n – 2}})\) M1A2
\({x_n} = 4{x_{n – 1}} – 3{x_{n – 2}}\) AG
we need to solve the quadratic equation \({t^2} – 4t + 3 = 0\) (M1)
\(t = 3,{\text{ }}1\) A1
\({x_n} = a \times {1^n} + b \times {3^n}\)
\({x_n} = a + b \times {3^n}\) A1
\(330 = a + b\) and \(420 = a + 3b\) M1
\(a = 285\) and \(b = 45\) A1
\({x_n} = 285 + 45 \times {3^n}\) A1
\({x_n} = 4{x_{n – 1}} – 3{x_{n – 2}}\)
\({x_n} = 285 + 45 \times {3^n}\)
let \(n = 0 \Rightarrow {x_0} = 330\) A1
let \(n = 1 \Rightarrow {x_1} = 420\) A1
hence true for \(n = 0,{\text{ }}n = 1\)
assume true for \(n = k,{\text{ }}{x_k} = 285 + 45 \times {3^k}\) M1
and assume true for \(n = k – 1,{\text{ }}{x_{k – 1}} = 285 + 45 \times {3^{k – 1}}\) M1
consider \(n = k + 1\)
\({x_{k + 1}} = 4{x_k} – 3{x_{k – 1}}\) M1
\({x_{k + 1}} = 4(285 + 45 \times {3^k}) – 3(285 + 45 \times {3^{k – 1}})\) A1
\({x_{k + 1}} = 4(285) – 3(285) + 4(45 \times {3^k}) – (45 \times {3^k})\) (A1)
\({x_{k + 1}} = 285 + 3(45 \times {3^k})\)
\({x_{k + 1}} = 285 + 45 \times {3^{k + 1}}\) A1
hence if solution is true for \(k\) and \(k – 1\) it is true for. However solution is true for \(k = 0\), \(k = 1\). Hence true for all \(k\). Hence proved by the principle of strong induction R1
Note: Do not award final reasoning mark unless candidate has been awarded at least 4 other marks in this part.
Question
The sequence \(\{ {u_n}:n \in {\mathbb{Z}^ + }\} \) satisfies the recurrence relation \(2{u_{n + 2}} – 3{u_{n + 1}} + {u_n} = 0\), where \({u_1} = 1,{\text{ }}{u_2} = 2\).
The sequence \(\{ {w_n}:n \in \mathbb{N}\} \) satisfies the recurrence relation \({w_{n + 2}} – 2{w_{n + 1}} + 4{w_n} = 0\), where \({w_0} = 0,{\text{ }}{w_1} = 2\).
(i) Find an expression for \({u_n}\) in terms of \(n\).
(ii) Show that the sequence converges, stating the limiting value.
The sequence \(\{ {v_n}:n \in {\mathbb{Z}^ + }\} \) satisfies the recurrence relation \(2{v_{n + 2}} – 3{v_{n + 1}} + {v_n} = 1\), where \({v_1} = 1,{\text{ }}{v_2} = 2\).
Without solving the recurrence relation prove that the sequence diverges.
(i) Find an expression for \({w_n}\) in terms of \(n\).
(ii) Show that \({w_{3n}} = 0\) for all \(n \in \mathbb{N}\).
Answer/Explanation
Markscheme
(i) the auxiliary equation is \(2{r^2} – 3r + 1 = 0\) (M1)
with roots \(r = 1,{\text{ }}\frac{1}{2}\) A1
the general solution of the difference equation is (M1)
\({u_n} = A + B{\left( {\frac{1}{2}} \right)^n}\) A1
imposing the initial conditions M1
\(A + \frac{B}{2} = 1,{\text{ }}A + \frac{B}{4} = 2\) A1
obtain \({u_n} = 3 – 4{\left( {\frac{1}{2}} \right)^n}\) A1
(ii) as \(n \to \infty ,{\text{ }}{\left( {\frac{1}{2}} \right)^n} \to 0\) R1
\({u_n} \to 3\) A1
hence the sequence is convergent AG
[9 marks]
assume \({v_n} \to L\) M1
taking the limit of both sides of the recurrence relation M1
\(2L – 3L + L{\text{ }}( = 0) = 1\) A1
the contradiction shows that the sequence diverges AG
[3 marks]
(i) the auxiliary equation \({r^2} – 2r + 4 = 0\) A1
has roots \(1 \pm {\text{i}}\sqrt 3 \) A1
METHOD 1
these can be re-expressed as \(2\left( {\cos \left( {\frac{\pi }{3}} \right) \pm {\text{i}}\sin \left( {\frac{\pi }{3}} \right)} \right)\) M1
the general solution is
\({w_n} = {2^n}\left( {A\cos \left( {\frac{{n\pi }}{3}} \right) + B\sin \left( {\frac{{n\pi }}{3}} \right)} \right)\) A1
imposing the initial conditions
\(A = 0,{\text{ }}2B\frac{{\sqrt 3 }}{2} = 2\) A1
obtain \({w_n} = \frac{{{2^{n + 1}}}}{{\sqrt 3 }}\sin \left( {\frac{{n\pi }}{3}} \right)\) A1
METHOD 2
the general solution is
\({w_n} = A{\left( {1 + {\text{i}}\sqrt 3 } \right)^n} + B{\left( {1 – {\text{i}}\sqrt 3 } \right)^n}\) A1
imposing the initial conditions
\(A + B = 0,{\text{ }}A + B + {\text{i}}\sqrt 3 (A – B) = 2\) M1A1
obtain \({w_n} = \frac{1}{{{\text{i}}\sqrt 3 }}{\left( {1 + {\text{i}}\sqrt 3 } \right)^n} – \frac{1}{{{\text{i}}\sqrt 3 }}{\left( {1 – {\text{i}}\sqrt 3 } \right)^n}\) A1
(ii) METHOD 1
\({w_{3n}} = \frac{{{2^{3n + 1}}}}{{\sqrt 3 }}\sin (n\pi )\) R1
\( = 0\) AG
METHOD 2
\({w_{3n}} = \frac{1}{{{\text{i}}\sqrt 3 }}{\left( {1 + {\text{i}}\sqrt 3 } \right)^{3n}} – \frac{1}{{{\text{i}}\sqrt 3 }}{\left( {1 – {\text{i}}\sqrt 3 } \right)^{3n}}\)
\( = \frac{1}{{{\text{i}}\sqrt 3 }}{( – 8)^n} – \frac{1}{{{\text{i}}\sqrt 3 }}{( – 8)^n}\) R1
\( = 0\) AG
[7 marks]
Question
The sequence \(\{ {u_n}\} \) satisfies the second-degree recurrence relation
\[{u_{n + 2}} = {u_{n + 1}} + 6{u_n},{\text{ }}n \in {\mathbb{Z}^ + }.\]
Another sequence \(\{ {v_n}\} \) is such that
\[{v_n} = {u_{2n}},{\text{ }}n \in {\mathbb{Z}^ + }.\]
Write down the auxiliary equation.
Given that \({u_1} = 12,{\text{ }}{u_2} = 6\), show that
\[{u_n} = 2 \times {3^n} – 3 \times {( – 2)^n}.\]
Determine the value of \(\mathop {\lim }\limits_{n \to \infty } \frac{{{u_n} + {u_{n – 1}}}}{{{u_n} – {u_{n – 1}}}}\).
Determine the second-degree recurrence relation satisfied by \(\{ {v_n}\} \).
Answer/Explanation
Markscheme
the auxiliary equation is \({m^2} – m – 6 = 0\) or equivalent A1
[??? marks]
attempt to solve quadratic (M1)
the roots are \(3,{\text{ }} – 2\) A1
the general solution is
\({u_n} = A \times {3^n} + B \times {( – 2)^n}\) A1
initial conditions give
\(3A – 2B = 12\)
\(9A + 4B = 6\) M1
the solution is \(A = 2,{\text{ }}B = – 3\) A1
\({u_n} = 2 \times {3^n} – 3 \times {( – 2)^n}\) AG
[??? marks]
\({u_n} + {u_{n – 1}} = 2 \times {3^n} – 3 \times {( – 2)^n} + 2 \times {3^{n – 1}} – 3 \times {( – 2)^{n – 1}}\) M1
\( = 8 \times {3^{n – 1}} + {\text{multiple of }}{2^{n – 1}}\) A1
\({u_n} – {u_{n – 1}} = 2 \times {3^n} – 3 \times {( – 2)^n} – 2 \times {3^{n – 1}} + 3 \times {( – 2)^{n – 1}}\)
\( = 4 \times {3^{n – 1}} + {\text{multiple of }}{2^{n – 1}}\) A1
any evidence of noting that the \({3^{n – 1}}\) terms dominate R1
\(\mathop {\lim }\limits_{n \to \infty } \frac{{{u_n} + {u_{n – 1}}}}{{{u_n} – {u_{n – 1}}}} = 2\) A1
[??? marks]
\({v_n} = 2 \times {3^{2n}} – 3 \times {( – 2)^{2n}}\) M1
\( = 2 \times {9^n} – 3 \times {4^n}\) A1
the auxiliary equation is
\({m^2} – 13m + 36 = 0\) A1
the recurrence relation is
\({v_{n + 2}} = 13{v_{n + 1}} – 36{v_n}\) A1
[4 marks]