Solve the recurrence relation ${u_n} = 4{u_{n - 1}} - 4{u_{n - 2}}$ given that ${u_0} = {u_1} = 1$.

Consider ${v_n}$ which satisfies the recurrence relation $2{v_n} = 7{v_{n - 1}} - 3{v_{n - 2}}$ subject to the initial conditions ${v_0} = {v_1} = 1$.

Prove by using strong induction that ${v_n} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^n} + \frac{1}{5}{\left( 3 \right)^n}$ for $n \in \mathbb{N}$.

auxiliary equation is ${m^2} - 4m + 4 = 0$      M1A1

hence $m$ has a repeated root of 2     (A1)

solution is of the form ${u_n} = a{\left( 2 \right)^n} + bn{\left( 2 \right)^n}$     M1

using the initial conditions      M1

$\Rightarrow a = 1$ and $b =  - \frac{1}{2}$

$\Rightarrow {u_n} = {2^n} - \frac{n}{2}{\left( 2 \right)^n}$      A1

[6 marks]

${v_n} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^n} + \frac{1}{5}{\left( 3 \right)^n}$

let $n = 0$  ${v_0} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^0} + \frac{1}{5}{\left( 3 \right)^0} = \frac{4}{5} + \frac{1}{5} = 1$

let $n = 1$  ${v_1} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^1} + \frac{1}{5}{\left( 3 \right)^1} = \frac{2}{5} + \frac{3}{5} = 1$

hence true for $n = 0$ and $n = 1$       M1A1

assume that ${v_j} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^j} + \frac{1}{5}{\left( 3 \right)^j}$ is true for all $j > k + 1$       M1

hence ${v_k} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^k} + \frac{1}{5}{\left( 3 \right)^k}$ and ${v_{k - 1}} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^{k - 1}} + \frac{1}{5}{\left( 3 \right)^{k - 1}}$

${v_{k + 1}} = \frac{{7{v_k} - 3{v_{k - 1}}}}{2}$

${v_{k + 1}} = \frac{{7\left[ {\frac{4}{5}{{\left( {\frac{1}{2}} \right)}^k} + \frac{1}{5}{{\left( 3 \right)}^k}} \right] - 3\left[ {\frac{4}{5}{{\left( {\frac{1}{2}} \right)}^{k - 1}} + \frac{1}{5}{{\left( 3 \right)}^{k - 1}}} \right]}}{2}$      M1A1

${v_{k + 1}} = \frac{{7\left[ {\frac{8}{5}{{\left( {\frac{1}{2}} \right)}^{k + 1}} + \frac{1}{{15}}{{\left( 3 \right)}^{k + 1}}} \right] - 3\left[ {\frac{{16}}{5}{{\left( {\frac{1}{2}} \right)}^{k + 1}} + \frac{1}{{45}}{{\left( 3 \right)}^{k + 1}}} \right]}}{2}$       (A1)

${v_{k + 1}} = \frac{{\frac{{56}}{5}{{\left( {\frac{1}{2}} \right)}^{k + 1}} + \frac{7}{{15}}{{\left( 3 \right)}^{k + 1}} - \frac{{48}}{5}{{\left( {\frac{1}{2}} \right)}^{k + 1}} - \frac{1}{{15}}{{\left( 3 \right)}^{k + 1}}}}{2}$       (A1)

${v_{k + 1}} = \frac{{\frac{8}{5}{{\left( {\frac{1}{2}} \right)}^{k + 1}} + \frac{6}{{15}}{{\left( 3 \right)}^{k + 1}}}}{2}$       (A1)

Note: Only one of the above (A1) can be implied.

${v_{k + 1}} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^{k + 1}} + \frac{1}{{15}}{\left( 3 \right)^{k + 1}}$

since the basis step and the inductive step have been verified, the Principle of Mathematical Induction tells us that ${v_n} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^n} + \frac{1}{5}{\left( 3 \right)^n}$ is
the general solution        R1

[9 marks]

Note: Only award final R1 if at least 5 previous marks have been awarded.