Problems

Filters
Clear Filters

4 problems found

2013 Paper 2 Q6
D: 1600.0 B: 1485.5
sequences recurrence relation convergence bounded and monotone proof by induction golden ratio subsequences fixed point

In this question, the following theorem may be used. Let \(u_1\), \(u_2\), \(\ldots\) be a sequence of (real) numbers. If the sequence is bounded above (that is, \(u_n\le b\) for all \(n\), where \(b\) is some fixed number) and increasing (that is, \(u_n \ge u_{n-1}\) for all \(n\)), then the sequence tends to a limit (that is, converges). The sequence \(u_1\), \(u_2\), \(\ldots\) is defined by \(u_1=1\) and \[ u_{n+1} = 1+\frac 1{u_n} \ \ \ \ \ \ \ \ \ \ (n\ge1)\,. \tag{\(*\)} \]

  1. Show that, for \(n\ge3\), \[ u_{n+2}-u_n = \frac{u_{n} - u_{n-2}}{(1+u_n)(1+u_{n-2})} . \]
  2. Prove, by induction or otherwise, that \(1\le u_n \le 2\) for all \(n\).
  3. Show that the sequence \(u_1\), \(u_3\), \(u_5\), \(\ldots\) tends to a limit, and that the sequence \(u_2\), \(u_4\), \(u_6\), \(\ldots\) tends to a limit. Find these limits and deduce that the sequence \(u_1\), \(u_2\), \(u_3\), \(\ldots\,\) tends to a limit. Would this conclusion change if the sequence were defined by \((*)\) and \(u_1=3\)?

Solution:

  1. \(\,\) \begin{align*} && u_{n+2} - u_n &= 1 + \frac{1}{u_{n+1}} - \left (1 + \frac{1}{u_{n-1}} \right) \\ &&&= \frac{1}{1 + \frac1{u_n}} - \frac{1}{1 + \frac{1}{u_{n-2}}} \\ &&&= \frac{u_n}{u_n+1} - \frac{u_{n-2}}{1+u_{n-2}} \\ &&&= \frac{u_n(1+u_{n-2}) - u_{n-2}(1+u_n)}{(1+u_n)(1+u_{n-2})} \\ &&&= \frac{u_n - u_{n-2}}{(1+u_n)(1+u_{n-2})} \end{align*}
  2. Claim: \(u_n \in [1,2]\) Proof: (By induction). Note that \(u_1 = 1, u_2 = 2\) so our claim is true for the first few terms. Note that if \(u_n \in [1,2]\), \(\frac{1}{u_n} \in [\tfrac12, 1]\) and \(1+\frac{1}{u_{n}} \in [\tfrac32,2] \subset [1,2]\). Therefore \(u_{n+1} \in [1,2]\). Therefore since \(u_1 \in [1,2]\) and \(u_n \in [1,2] \Rightarrow u_{n+1} \in [1,2]\) \(u_n \in [1,2]\) for all \(n \ge 1\)
  3. First notice that \(u_3 = \frac32 > u_1\) and therefore by the recursion we found in the first part, \(u_{2n+1}-u_{2n-1} > 0\) so \(u_{2k+1}\) is increasing and bounded, and so by our theorem converges to a limit. Suppose this limit is \(L\), then we must have \(L = 1 + \frac1{L} \Rightarrow L^2 - L - 1 = 0 \Rightarrow L = \frac{1+\sqrt5}{2}\) since it must be in \([1,2]\). Similarly, not that \(u_4 = \frac{5}{3} < u_2\) and so \(u_{2k+2} - u_{2k} < 0\) and \(-u_{2k}\) is increasing and bounded above. Therefore it tends to a limit (and so does \(u_{2k}\)). By the same reasoning as before, it's the same limit, \(\frac{1+\sqrt5}{2}\) and therefore the sequence converges. If \(u_1 = 3, u_2 = \frac43 \in [1,2]\) so we have our sequence being bounded and all the same logic will follow through.

View
2010 Paper 2 Q3
D: 1600.0 B: 1500.0
sequences Fibonacci sequence recurrence relation golden ratio simultaneous equations geometric series infinite series

The first four terms of a sequence are given by \(F_0=0\), \(F_1=1\), \(F_2=1\) and \(F_3=2\). The general term is given by \[ F_n= a\lambda^n+b\mu^n\,, \tag{\(*\)} \] where \(a\), \(b\), \(\lambda\) and \(\mu\) are independent of \(n\), and \(a\) is positive.

  1. Show that \(\lambda^2 +\lambda\mu+ \mu^2 = 2\), and find the values of \(\lambda\), \(\mu\), \(a\) and \(b\).
  2. Use \((*)\) to evaluate \(F_6\).
  3. Evaluate \(\displaystyle \sum_{n=0}^\infty \frac{F_n}{2^{n+1}}\,.\)

Solution:

  1. \(\,\) \begin{align*} && 0 &= a+b \tag{1}\\ && 1 &= a\lambda -a\mu \tag{2} \\ && 1 &= a\lambda^2 -a\mu^2 \tag{3} \\ && 2 &= a\lambda^3 - a\mu^3 \tag{4} \\ (4) \div (2): && 2 & = \lambda^2+\lambda \mu + \mu^2 \\ (3) \div (2): && 1 &= \lambda + \mu \\ \Rightarrow && 2 &= \lambda^2 + \lambda(1-\lambda) + (1-\lambda)^2 \\ &&&= \lambda^2-\lambda+1\\ \Rightarrow && \lambda, \mu &= \frac{1 \pm \sqrt{5}}{2} \\ \Rightarrow && a &= \frac{1}{\lambda - \mu} = \frac{1}{\sqrt{5}} \\ \Rightarrow && b &= -\frac{1}{\sqrt{5}} \end{align*} (NB: This is Binet's formula)
  2. \(\,\) \begin{align*} F_6 &= \frac{1}{\sqrt{5}} \left ( \left ( \frac{1 +\sqrt{5}}{2} \right)^6- \left ( \frac{1 -\sqrt{5}}{2} \right)^6 \right) \\ &= \frac{1}{2^6 \sqrt{5}} \left ( (1+\sqrt{5})^6-(1-\sqrt{5})^6 \right) \\ &= \frac{1}{2^5 \cdot \sqrt{5}} \left (6 \sqrt{5} +\binom{6}{3} (\sqrt{5})^3+\binom{6}{5}(\sqrt{5})^5 \right)\\ &= \frac{1}{2^5} \left (6 +20\cdot 5+6\cdot 5^2 \right)\\ &= \frac{1}{2^5} 256 = 2^3 = 8 \end{align*} (way more painful than just computing it by adding terms!)
  3. \(\,\) \begin{align*} && \sum_{n=0}^{\infty} \frac{F_n}{2^{n+1}} &= \sum_{n=0}^{\infty} \frac{a\lambda^n + b\mu^n}{2^{n+1}} \\ &&&= \frac12 \left ( \frac{a}{1-\frac{\lambda}2} + \frac{b}{1-\frac{\mu}2} \right) \\ &&&= \frac12 \left ( \frac{2a}{2-\lambda} + \frac{2b}{2-\mu}\right) \\ &&&= \frac{2a}{4-2\lambda} + \frac{2b}{4-2\mu}\\ &&&= \frac{2a}{4-(1+\sqrt{5})} - \frac{2a}{4-(1-\sqrt{5})} \\ &&&= \frac{2}{3\sqrt{5}-5} - \frac{2}{3\sqrt{5}+5} \\ &&&= \frac{6\sqrt{5}+10-6\sqrt{5}+10}{45-25} \\ &&&= 1 \end{align*}

View
2000 Paper 3 Q8
D: 1700.0 B: 1484.0
sequences recurrence relation proof by induction auxiliary equation golden ratio nonlinear recurrence closed form

The sequence \(a_n\) is defined by \(a_0 = 1\) , \(a_1 = 1\) , and $$ a_n = {1 + a_{n - 1}^2 \over a_{n - 2} } \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ( n \ge 2 ) . $$ Prove by induction that $$ a_n = 3 a_{n - 1} - a_{n - 2} \ \ \ \ \ \ \ \ \ \ \ ( n \ge2 ) . $$ Hence show that $$ a_n = {\alpha^{2 n - 1} + \alpha^{- ( 2 n - 1 )} \over \sqrt 5} \ \ \ \ \ \ (n\ge1), $$ where \(\displaystyle{\alpha = {1 + \sqrt 5 \over 2}}\).

View
1999 Paper 1 Q3
D: 1500.0 B: 1500.0
inequalities sequences recurrence relation proof by contradiction quadratics cyclic system golden ratio

The \(n\) positive numbers \(x_{1},x_{2},\dots,x_{n}\), where \(n\ge3\), satisfy $$ x_{1}=1+\frac{1}{x_{2}}\, ,\ \ \ x_{2}=1+\frac{1}{x_{3}}\, , \ \ \ \dots\; , \ \ \ x_{n-1}=1+\frac{1}{x_{n}}\, , $$ and also $$ \ x_{n}=1+\frac{1}{x_{1}}\, . $$ Show that

  1. \(x_{1},x_{2},\dots,x_{n}>1\),
  2. \({\displaystyle x_{1}-x_{2}=-\frac{x_{2}-x_{3}}{x_{2}x_{3}}}\),
  3. \(x_{1}=x_{2}=\cdots=x_{n}\).
Hence find the value of \(x_1\).

View