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.