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.