sequences and series - Limit of a non-monotonic recurrence relation

I want to show the limit of recurrence $a_{n+1}=1/(1+a_n)$ exists with $a_1= 0.5$. I can find the limit, and I can see that sequence is oscillating. but proving it is being difficult to me. In general is there a method to prove the convergence of such non monotonic sequences, without bringing in matrices and Eigen vectors? So that I can apply it to other converging oscillating sequences.

Answer

One strategy to solve a recurrence relation is the "Guess and Verify" method.

Guess the answer, and then verify it is correct by whatever means.

For this problem, assume a limit $\lambda$ exists, the recurrence
$a_{n+1} = \frac{1}{1+a_n}$ tell us $\lambda$ "should" satisfy

$$\lambda = \frac{1}{1+\lambda} \iff \lambda^2 + \lambda - 1 \implies \lambda = \phi^{-1} \text{ or } -\phi$$
where $\phi = \frac{1+\sqrt{5}}{2}$ is the golden ratio. It is clear start from any positive $a_1$, all remaining $a_n$ will be positive. So the desired limit, if exists, cannot be $-\phi$. This make $\lambda = \phi^{-1}$ of our own candidate as the limit.

To verify $\phi^{-1}$ is indeed the limit. One most approach is compare the absolute difference between it and successive terms of the sequence and see what one can get. For any $n \ge 1$, we have

$$\left|a_{n+1} - \phi^{-1}\right| =
\left|\frac{1}{1+a_n} - \frac{1}{1+\phi^{-1}}\right|
= \left|\frac{a_n - \phi^{-1}}{(1+a_n)(1+\phi^{-1})}\right|
\le \left|\frac{a_n - \phi^{-1}}{1+\phi^{-1}}\right|
= \phi^{-1}\left|a_n - \phi^{-1}\right|

$$
Repeating apply this inequality, we find for any $n > 1$,

$$|a_n - \phi^{-1}| \le \phi^{-1}|a_{n-1}-\phi^{-1}|
\le \phi^{-2}|a_{n-2}-\phi^{-1}| \le \cdots \le \phi^{1-n}|a_1 - \phi^{-1}|$$

Since $|\phi^{-1}| < 1$, $\lim_{n\to\infty} \phi^{1-n} = 0$ and verify our guess:
$$\lim_{n\to\infty} a_n = \phi^{-1} = \frac{\sqrt{5}-1}{2}$$

Update

If one cannot figure out the limit, there are others approaches one can try.

For this particular problem, one can use contraction mapping theorem.

Given any function $f : [a,b] \to [a,b]$. If for some $K < 1$,
$|f(x)-f(y)| \le K|x-y|$ for all $x, y \in [a,b]$, then

• $f(x)$ has a unique fixed point $\lambda$ over [a,b].


• Start from any $c \in [a,b]$, the sequence $(c_n)_{n\ge 1}$ obtained by repeat iteration of $f(x)$ $$c_1 = c\quad\text{ and }\quad c_n = f(c_{n-1})\text{ for } n > 1$$
  converges to this $\lambda$.

Take $f(x) = \frac{1}{1+x}$, it is easy to see $f([\frac12,1]) = [\frac12,\frac13]$. Notice for any $x,y \in [\frac12, 1]$, we have
$$|f(x) - f(y)| = \left|\frac{1}{1+x}-\frac{1}{1+y}\right|
= \left|\frac{x-y}{(1+x)(1+y)}\right| \le \frac49|x-y|$$
This $f(x)$ is a contraction mapping over $[\frac12,1]$.

Start from any $c \in [\frac12,1]$, the sequence obtained by repeating iteration of $f(x)$ converges to the unique fixed point of $f(x)$. This includes the sequence $a_n$ at hand which corresponds to $c = \frac12$.