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{\(*\)}
\]
Show that, for \(n\ge3\),
\[
u_{n+2}-u_n = \frac{u_{n} - u_{n-2}}{(1+u_n)(1+u_{n-2})}
.
\]
Prove, by induction or otherwise, that \(1\le u_n \le 2\) for all \(n\).
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\)?
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\)
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.