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 .

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

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]