The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

The Computer Laboratory

Practice Paper 3 Question 7

Let \(a_n, b_n\) be sequences of positive real numbers which satisfy \(a_0 = b_0\) and the recursive matrix relation \(\big(\begin{smallmatrix}a_n \\b_n\end{smallmatrix}\big)=\big(\begin{smallmatrix} 1 & y \\0 & 1\end{smallmatrix}\big)\big(\begin{smallmatrix}a_{n-1} \\b_{n-1}\end{smallmatrix}\big).\) What is the simplest non-recursive form of the ratio \(\frac{b_n}{a_n}?\)

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Hints

  • Hint 1
    Evaluate \(\big(\begin{smallmatrix}1 & y \\0 & 1\end{smallmatrix}\big)\big(\begin{smallmatrix}u \\v\end{smallmatrix}\big).\)
  • Hint 2
    Try to express the relationship between \(\big(\begin{smallmatrix}a_n \\ b_n\end{smallmatrix}\big)\) and \(\big(\begin{smallmatrix}a_0 \\ b_0\end{smallmatrix}\big)\) as a non-recursive matrix equation.
  • Hint 3
    Simplify \({\big(\begin{smallmatrix}1 & y \\0 & 1\end{smallmatrix}\big)}^n,\) by trying small values of \(n\) or otherwise.

Solution

We can unwind this matrix recurrence in the same way as a regular recurrence, \(\big(\begin{smallmatrix} a_n \\ b_n \end{smallmatrix}\big) = \big(\begin{smallmatrix} 1 & y \\ 0 & 1 \end{smallmatrix}\big) \big(\begin{smallmatrix} a_{n-1} \\ b_{n-1} \end{smallmatrix}\big)\) \(={\big(\begin{smallmatrix} 1 & y \\ 0 & 1 \end{smallmatrix}\big)}^2 \big(\begin{smallmatrix} a_{n-2} \\ b_{n-2} \end{smallmatrix}\big)\) \(=\ldots=\) \({\big(\begin{smallmatrix} 1 & y \\ 0 & 1 \end{smallmatrix}\big)}^n \big(\begin{smallmatrix} a_{0} \\ b_{0} \end{smallmatrix}\big).\) Using induction, we can show that \({\big(\begin{smallmatrix} 1 & y \\ 0 & 1 \end{smallmatrix}\big)}^n\) \(={\big(\begin{smallmatrix} 1 & ny \\ 0 & 1 \end{smallmatrix}\big)}.\) Hence, \(\big(\begin{smallmatrix} a_n \\ b_n \end{smallmatrix}\big)\) \(={\big(\begin{smallmatrix} 1 & ny \\ 0 & 1 \end{smallmatrix}\big)} \big(\begin{smallmatrix} a_{0} \\ b_{0} \end{smallmatrix}\big)\) \(=\big(\begin{smallmatrix} a_{0} + nyb_{0} \\ b_{0} \end{smallmatrix}\big).\) Therefore the ratio \(\frac{b_n}{a_n}\) is \(\frac{b_0}{a_0 + nyb_0} = \frac{1}{1+ny}.\)

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.foo[email protected]. Please do not write to this address regarding general admissions or course queries.