Download IITian Academy App for accessing Online Mock Tests and More..
Question
Consider the recurrence relation \({H_{n + 1}} = 2{H_n} + 1,{\text{ }}n \in {\mathbb{Z}^ + }\) where \({H_1} = 1\).
Find \({H_2}\), \({H_3}\) and \({H_4}\).
Conjecture a formula for \({H_n}\) in terms of \(n\), for \(n \in {\mathbb{Z}^ + }\).
Prove by mathematical induction that your formula is valid for all \(n \in {\mathbb{Z}^ + }\).
Answer/Explanation
Markscheme
\({H_2} = 2{H_1} + 1\) (M1)
\( = 3;{\text{ }}{H_3} = 7;{\text{ }}{H_4} = 15\) A1
[2 marks]
\({H_n} = {2^n} – 1\) A1
[1 mark]
let \({\text{P}}(n)\) be the proposition that \({H_n} = {2^n} – 1\) for \(n \in {\mathbb{Z}^ + }\)
from (a) \({H_1} = 1 = {2^1} – 1\) A1
so \({\text{P}}(1)\) is true
assume \({\text{P}}(k)\) is true for some \(k \Rightarrow {H_k} = {2^k} – 1\) M1
then \({H_{k + 1}} = 2{H_k} + 1\) (M1)
\( = 2 \times ({2^k} – 1) + 1\) A1
\( = {2^{k + 1}} – 1\)
\({\text{P}}(1)\) is true and \({\text{P}}(k)\) is true \( \Rightarrow {\text{P}}(k + 1)\) is true, hence \({\text{P}}(n)\) is true for all \(n \in {\mathbb{Z}^ + }\) by the principle of mathematical induction R1
Note: Only award the R1 if all earlier marks have been awarded.
[5 marks]
Question
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}\).
Answer/Explanation
Markscheme
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.
Question
A sequence \(\left\{ {{u_n}} \right\}\) satisfies the recurrence relation \({u_{n + 2}} = 2{u_{n + 1}} – 5{u_n}\) , \(n \in \mathbb{N}\) . Obtain an expression for \({u_n}\) in terms of n given that \({u_0} = 0\) and \({u_1} = 1\) .
Answer/Explanation
Markscheme
the auxiliary equation is \({m^2} – 2m + 5 = 0\) M1
the roots are \(1 \pm 2{\rm{i}}\) A1
the general solution is \({u_n} = A{\left(1 + 2{\rm{i}}\right)^n} + B{\left(1 – 2{\rm{i}}\right)^n}\) A1
substituting \({u_0} = 0\) and \({u_1} = 1\) M1
\(A + B = 0\)
\(A(1 + 2{\rm{i}}) + B(1 – 2{\rm{i}}) = 1\) A1
Note: Only award above A1 if both equations are correct.
solving
\(A\left(1 + 2{\rm{i}} – 1 + 2{\rm{i}}\right) = 1\) (M1)
\(A = \frac{1}{{4{\rm{i}}}}\) or \( – \frac{{\rm{i}}}{4}\) A1
\(B = – \frac{1}{{4{\rm{i}}}}\) or \(\frac{{\rm{i}}}{4}\) A1
therefore
\({u_n} = \frac{1}{{4{\rm{i}}}}{\left(1 + 2{\rm{i}}\right)^n} – \frac{1}{{4{\rm{i}}}}{\left(1 – 2{\rm{i}}\right)^n}\) or \(\frac{{\rm{i}}}{4}{\left(1 – 2{\rm{i}}\right)^n} – \frac{{\rm{i}}}{4}{\left(1 + 2{\rm{i}}\right)^n}\) A1
[9 marks]