Problems

Filters
Clear Filters

2 problems found

2017 Paper 1 Q8
D: 1500.0 B: 1516.0
proof by induction sequences recurrence relation convergence inequality rational approximation quadratic identity sqrt(2)

Two sequences are defined by \(a_1 = 1\) and \(b_1 = 2\) and, for \(n \ge 1\), \begin{equation*} \begin{split} a_{n+1} & = a_n+ 2b_n \,, \\ b_{n+1} & = 2a_n + 5b_n \,. \end{split} \end{equation*} Prove by induction that, for all \(n \ge 1\), \[ a_n^2+2a_nb_n - b_n^2 = 1 \,. \tag{\(*\)}\]

  1. Let \(c_n = \dfrac{a_n}{b_n}\). Show that \(b_n \ge 2 \times 5^{n-1}\) and use \((*)\) to show that \[ c_n \to \sqrt 2 -1 \text{ as } n\to\infty\,. \]
  2. Show also that \(c_n > \sqrt2 -1\) and hence that \(\dfrac2 {c_n+1} < \sqrt2 < c_n+1\). Deduce that \(\dfrac{140}{99}< \sqrt{2} < \dfrac{99}{70 }\,\).

Solution: Claim \(a_n^2+2a_nb_n - b_n^2 = 1\) for all \(n \geq 1\) Proof: (By induction) Base case: (\(n = 1\)). When \(n = 1\) we have \(a_1^2 + 2a_1 b_1-b_1^2 = 1^2+2\cdot1\cdot2-2^2 = 1\) as required. (Inductive step). Now we assume our result is true for some \(n =k\), ie \(a_k^2+2a_kb_k - b_k^2 = 1\), now consider \(n = k+1\) \begin{align*} && a_{k+1}^2+2a_{k+1}b_{k+1} - b_{k+1}^2 &= (a_k+2b_k)^2+2(a_k+2b_k)(2a_k+5b_k) - (2a_k+5b_k)^2 \\ &&&= a_k^2+4a_kb_k+4b_k^2 +4a_k^2+18a_kb_k+20b_k^2 - 4a_k^2-20a_kb_k-25b_k^2 \\ &&&= (1+4-4)a_k^2+(4+18-20)a_kb_k +(4+20-25)b_k^2 \\ &&&= a_k^2+2a_kb_k -b_k^2 = 1 \end{align*} Therefore since our statement is true for \(n = 1\) and when it is true for \(n=k\) it is true for \(n=k+1\) by the POMI it is true for \(n \geq 1\)

  1. Notice that \(b_{n+1} \geq 5 b_n\) and therefore \(b_n \geq 5^{n-1} b_1 = 2\cdot 5^{n-1}\), so \begin{align*} && 1 &= a_n^2+2a_nb_n - b_n^2\\ \Rightarrow && \frac1{b_n^2} &= c_n^2 + 2c_n - 1 \\ \to && 0 &= c_n^2 + 2c_n - 1 \quad \text{ as } n\to \infty \\ \end{align*} This has roots \(c = -1 \pm \sqrt{2}\), and since \(c_n > 0\) it must tend to the positive value, ie \(c_n \to \sqrt{2}-1\)
  2. Notice that \(c_n^2 + 2c_n - 1 > 0\) so either \(c_n > \sqrt{2}-1\) or \(c_n < -1-\sqrt{2}\), but again, since \(c_n > 0\) we must have \(c_n > \sqrt{2}-1\). Therefore \(\sqrt{2} < c_n + 1\) and \(1+c_n > \sqrt{2} \Rightarrow \frac{1}{1+c_n} < \frac{\sqrt{2}}2 \Rightarrow \frac{2}{1+c_n} < \sqrt{2}\) \begin{array}{c|c|c} n & a_n & b_n \\ \hline 1 & 1 & 2 \\ 2 & 5 & 12 \\ 3 & 29 & 70 \end{array} Therefore \(c_3 = \frac{29}{70}\) and so \(\frac{2}{1 + \frac{29}{70}} = \frac{140}{99} < \sqrt{2} < \frac{29}{70} + 1 = \frac{99}{70}\)

View
2004 Paper 3 Q6
D: 1700.0 B: 1503.0
sequences recurrence relation quadratic identity algebraic manipulation periodic sequence proof telescoping

Given a sequence \(w_0\), \(w_1\), \(w_2\), \(\ldots\,\), the sequence \(F_1\), \(F_2\), \(\ldots\) is defined by $$F_n = w_n^2 + w_{n-1}^2 - 4w_nw_{n-1} \,.$$ Show that $\; F_{n}-F_{n-1} = \l w_n-w_{n-2} \r \l w_n+w_{n-2}-4w_{n-1} \r \; \( for \)n \ge 2\,$.

  1. The sequence \(u_0\), \(u_1\), \(u_2\), \(\ldots\) has \(u_0 = 1\), and \(u_1 = 2\) and satisfies \[ u_n = 4u_{n-1} -u_{n-2} \quad (n \ge 2)\;. \] Prove that \ $ u_n^2 + u_{n-1}^2 = 4u_nu_{n-1}-3 \; $ for \(n \ge 1\,\).
  2. A sequence \(v_0\), \(v_1\), \(v_2\), \(\ldots\,\) has \(v_0=1\) and satisfies \begin{equation*} v_n^2 + v_{n-1}^2 = 4v_nv_{n-1}-3 \quad (n \ge 1). \tag{\(\ast\)} \end{equation*} \makebox[7mm]{(a) \hfill}Find \(v_1\) and prove that, for each \(n\ge2\,\), either \(v_n= 4v_{n-1} -v_{n-2}\) or \(v_n=v_{n-2}\,\). \makebox[7mm]{(b) \hfill}Show that the sequence, with period 2, defined by \begin{equation*} v_n = \begin{cases} 1 & \mbox{for \(n\) even} \\ 2 & \mbox{for \(n\) odd} \end{cases} \end{equation*} \makebox[7mm]{\hfill}satisfies \((\ast)\). \makebox[7mm]{(c) \hfill}Find a sequence \(v_n\) with period 4 which has \(v_0=1\,\), and satisfies~\((\ast)\).

View