Is the sequence defined by $a_{n+1} = \frac{1}{a_n} + 1$ convergent?

Question

The sequence defined by $a_1=1$ and $$a_{n+1} = \frac{1}{a_n} + 1$$ is increasing. And I can get the limit which is equal to $$\frac{1+\sqrt{5}}{2}$$ But $a_2 = 2$ which is larger than the limit. So is the sequence convergent or divergent?

Answer 1

Rather surprisingly, the answers already posted deal with the convergence of the sequence $(a_n)$ by invoking known results about the convergents of continued fractions and/or known results about Fibonacci sequences, that is, they basically deduce this convergence from some more involved results. It happens that one can solve the exercise without relying on such higher level knowledge. Rather, it suffices to apply some standard techniques of real analysis, and, since these basic techniques are, imnsho, worth knowing for themselves anyway... here we go.

---

1. The sequence $(a_n)$ is defined recursively by $a_1=1$ and $a_{n+1}=f(a_n)$ for every $n\geqslant1$, with $f(x)=1+\frac1x$. One of the first impulses here should be to study the properties of the function $f$ itself, and, more precisely, to check whether this function is a contraction, that is, whether one can find some $k<1$ such that $|f(x)-f(y)|\leqslant k\cdot|x-y|$ for every $(x,y)$.

2. If ever one succeeds in showing this, it is a quite general fact that then, for every $n$, $|a_{n+1}-a_n|\leqslant k^{n-1}\cdot|a_2-a_1|$ hence the series $\sum\limits_n(a_{n+1}-a_n)$ is absolutely convergent hence $\sum\limits_{n=1}^{N-1}(a_{n+1}-a_n)=a_N-a_1$ converges to some limit $s$, hence $a_N\to a_1+s$, and the proof of the convergence of $(a_n)$ is over.

3. Now, as everybody knows, a convenient tool to check that some function is a contraction is its derivative (when it exists). Here, $f'(x)=-\frac1{x^2}$ hence $|f'|\leqslant k$ does not hold everywhere, for any $k$. Does this mean we reached a dead end and that we should abandon all hope?

...Not quite, since $|f'|\leqslant 1$ on $[1,+\infty)$ and even, $|f'|\leqslant k$ with $k<1$ on $[c,+\infty)$, for each $c>1$, hence a way out would be to prove that the behaviour of $f$ is only relevant on some $[c,+\infty)$ with $c>1$.

4. But $a_1=1$ hence, a priori, one needs $f$ on $[1,+\infty)$, which is already better but not good enough yet. Only, if one looks better... one can note that $a_2=2$ and $a_3=\frac32$ are both strictly larger than $1$. Furthermore, $f$ is decreasing on $[1,+\infty)$ hence $\frac32\leqslant a_n\leqslant2$ implies $f(2)\leqslant f(a_n)\leqslant f(\frac32)$, that is, $\frac32\leqslant a_{n+1}\leqslant\frac53$ and in particular, $\frac32\leqslant a_{n+1}\leqslant2$.

5. Thus, $\frac32\leqslant a_n\leqslant2$ for every $n\geqslant2$ and now, everything goes smoothly since only the interval $[\frac32,2]$ is relevant and $|f'|\leqslant\frac49$ on $[\frac32,2]$. To sum up, $f$ is a contraction on this interval and the general argument above applies with $k=\frac49$, which ends the proof that $(a_n)$ converges.

6. To identify the limit, one proceeds as usual: if $a_n\to\ell$, then $a_{n+1}=f(a_n)\to f(\ell)$ because $f$ is continuous hence $\ell=f(\ell)$, that is, $\ell$ is a fixed point of $f$. One knows that $\ell\geqslant1$ since $a_n\geqslant1$ for every $n\geqslant1$, hence $\ell=\frac12(1+\sqrt5)$, which ends the proof that $(a_n)$ converges to $\frac12(1+\sqrt5)$.

R1. One remark: one could also first identify $\ell$, solving $f(\ell)=\ell$, and then prove somewhat more easily the convergence to $\ell$ through the inequalities $|a_{n+1}-\ell|=|f(a_n)-f(\ell)|\leqslant k\cdot|a_n-\ell|$, which imply $|a_n-\ell|\leqslant k^{n-1}\cdot|a_1-\ell|\to0$, hence $a_n\to\ell$, qed.

R2. And one last remark: nowhere does one compute the general term $a_n$ as an explicit function of $n$. This is a huge advantage in situations where such explicit computations are impossible. Thus...

C. To conclude, focussing on the properties of the function $f$ was definitely a good idea since this provided a solution to this specific exercise but also, perhaps more importantly, because this provided a deep understanding of the reasons why this specific result holds, and also because this showed how to solve, using some quite flexible techniques, a wealth of other similar questions.

Answer 2

It is convergent, but you're wrong about it being increasing. In fact, it is oscillating. Let $a_1=1$: $$a_2=\frac{1}{1}+1>1=a_1$$ $$a_3=\frac{1}{2}+1<2=a_2$$ $$a_4=\frac{2}{3}+1>\frac{3}{2}=a_3$$ $$a_5=\frac{3}{5}+1<\frac{5}{3}=a_4$$

One way to prove this sequence converges is to connect this sequence with the notion of a Continued Fraction, and to realize that your sequence is the sequence of convergents of $\phi=\frac{1+\sqrt{5}}{2}$. The convergence follows from the "Useful Theorems" section of that link.

Alternatively, consider the even and odd indexed sequences ($a_{2i+1}$ and $a_{2i}$). Each of those is monotonic (in different directions) and bounded and so is convergent. Now you just need to show that they converge to the same value by showing the inf of the decreasing sequence equals the sup of the increasing sequence.

Answer 3

$a_{n+1}-a_n=\frac{-a_n^2+a_n+1}{a_n}=-\frac{1}{a_n}(a_n-\rho)(a_n+\frac{1}{\rho})$ where $\rho=\frac{1+\sqrt5}{2}$.

So $(a_n)$ is not increasing : $a_{n+1}\ge a_n$ if $0< a_n\le \rho$, and $a_{n+1}\le a_n$ if $\rho<a_n$.

The function $x\mapsto \frac1x+1$ is decreasing, so the convergence to $\rho$ is not monotonous. Check again your computations.

Answer 4

$\begin{array}\\ a_{n+1} &=1+ \frac{1}{a_n}\\ &=1+ \frac{1}{1+ \frac{1}{a_{n-1}}}\\ &=1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{a_{n-2}}}}\\ &...\\ &=1+ \frac1{1+ \frac1{1+ \frac1{1+...}}} \qquad n \text{ deep}\\ \end{array} $

But that continued fraction is $\dfrac{F_{n+1}}{F_n} \to \phi $.