Solve the recurrence relation ${v_n} + 4{v_{n - 1}} + 4{v_{n - 2}} = 0$ where ${v_1} = 0,{\text{ }}{v_2} = 1$.

Use strong induction to prove that the solution to the recurrence relation ${u_n} - 4{u_{n - 1}} + 4{u_{n - 2}} = 0$ where ${u_1} = 0,{\text{ }}{u_2} = 1$ is given by ${u_n} = {2^{n - 2}}(n - 1)$.

Find a simplified expression for ${u_n} + {v_n}$ given that,

(i)     $n$ is even.

(ii)     $n$ is odd.

the auxiliary equation is ${m^2} + 4m + 4 = 0$     M1

$m = -2$    A1

the general solution is

${v_n} = (A + Bn) \times {( - 2)^n}$    A1

the boundary conditions give

$0 = -{\text{ }}2(A + B)$

$1 = 4(A + 2B)$    M1

the solution is $A =  - \frac{1}{4},{\text{ }}B = \frac{1}{4}$     A1A1

so that ${v_n} = \frac{1}{4}(n - 1){( - 2)^n}{\text{ }}\left( {{\text{or }}(n - 1)( - 2{)^{n - 2}}} \right)$

[6 marks]

$n = 1$ gives $(1 - 1) \times \frac{1}{2} = 0$ which is correct     A1

$n = 2$ gives $(2 - 1) \times 1 = 1$ which is correct     A1

Note:     Must be checked for $n = 1$ and 2, other values gain no marks.

assume that the result is true for all positive integers $\leqslant k$     M1

${u_{k + 1}} = 4{u_k} - 4{u_{k - 1}}$    (M1)

${u_{k + 1}} = 4 \times {2^{k - 2}}(k - 1) - 4 \times {2^{k - 3}}(k - 2)$    A1

$= {2^{k - 1}}(2k - 2 - k + 2)$ or equivalent     A1

$= k{2^{k - 1}}$    A1

therefore true for $n \leqslant k \Rightarrow$ true for $n = k + 1$ and since true for $n = 1$ and $n = 2$, the result is proved by strong induction     R1

Note:     Only award the R1 if at least four of the above marks have been awarded.

Note:     Allow true for $k$ and $k - 1$ (in 2 places) instead of stronger statement.

Note:     First M1 does not have to be given for further marks to be gained but second (M1) does.

[8 marks]

(i)     ${u_n} + {v_n} = {2^{n - 2}}(n - 1) + {( - 2)^{n - 2}}(n - 1)$

when $n$ is even ${u_n} + {v_n} = {2^{n - 2}}(n - 1) + {2^{n - 2}}(n - 1)$     M1

$= {2^{n - 1}}(n - 1)$    A1

(ii)     when $n$ is odd ${u_n} + {v_n} = 0$     A1

[3 marks]

This was either done well and completely correct or very little achieved at all (working out ${v_0}$ for some reason). As expected a few candidates forgot what to do for a repeated root. The varied response to this question was surprising since it is just standard book work.

Strong induction proved to be a very good discriminator. Some candidates knew exactly what to do and did it well, others had no idea. Common mistakes were not checking $n = 2$ and 2, trying ordinary induction and worse of all assuming the very thing that they were trying to prove.

Most candidates that had the 2 expressions, knew how to get rid of the minus sign in the 2 cases. Some candidates could not attempt this as they had not completed part (a) although when it was wrong, follow through marks could be obtained.