Proof that if $a_1=1$ and $a_{n+1}=1+\frac{1}{1+a_n}$

Question: Prove that if

$$a_n=\left\{ \begin{array}{ll} a_1=1\\ a_{n+1}=1+\frac{1}{1+a_n} \end{array} \right.$$ then $a_n$ converges, and then find $\lim_{n \to \infty}a_n$.

I found that $\lim_{n \to \infty}a_n=\sqrt{2}$, and that $1\leq a_n<2$, but the convergence seems difficult.

My idea is to show that $a_{2n}$ is decreasing, and $a_{2n-1}$ is increasing, but I don’t see how.

I’d be thankful for any hint.

Note that on $[1,2]$ the function $f(x) = 1 + {1 \over 1 + x}$ satisfies $|f'(x)| \leq {1 \over 4}$. So by the mean-value theorem, for $x$ and $y$ in the interval you have $|f(x) - f(y)| \leq {1 \over 4}|x - y|$. Letting $x = a_n$ and $y = a_{n+1}$ this implies that
$$|a_{n+2} - a_{n+1}| \leq {1 \over 4}|a_{n+1} - a_n| $$ Writing $a_n = (a_n - a_{n-1}) + (a_{n-1} - a_{n-2}) + ... + (a_2 - a_1) + a_1$, it's not too hard to use the above equation to show that the $a_n$ are a Cauchy sequence and therefore converge.

The above is an adaptation of the proof of the contraction mapping theorem by the way.

Clearly $a_n>1$. Note $$|a_{n+1}-\sqrt{2}|=\frac{\sqrt{2}-1}{1+a_n}|a_n-\sqrt{2}|\le\frac{\sqrt{2}-1}{2}|a_n-\sqrt{2}|.$$ Thus $$|a_n-\sqrt{2}|\le \left(\frac{\sqrt{2}-1}{2}\right)^{n-1}|a_1-\sqrt{2}|$$ and hence $$\lim_{n\to\infty}a_n=\sqrt{2}.$$

Given

$$ a_{n+1} = 1 + \frac{ 1 }{ 1 + a_n }. $$

Which can be written as

$$ a_{n+1} = \frac{ 2 + a_n }{ 1 + a_n }. $$

Write

$$ a_n = \frac{ P_n }{ Q_n }, $$

then

$$ a_{n+1} = \frac{ 2 + a_n }{ 1 + a_n } = \frac{ \displaystyle 2 + \frac{ P_n }{ Q_n } }{ \displaystyle 1 + \frac{ P_n }{ Q_n } } = \frac{ P_n + 2Q_n }{ P_n + Q_n } = \frac{ P_{n+1} }{ Q_{n+1} }. $$

Thus we have the recursion

$$ \begin{eqnarray} P_{n+1} &=& P_n + 2 Q_n,\\ Q_{n+1} &=& P_n + Q_n. \end{eqnarray} $$

Note that

$$ \begin{eqnarray} P_{n+1} + \sqrt{2} Q_{n+1} &=& \Big( 1 + \sqrt{2} \Big) \Big( P_{n} + \sqrt{2} Q_{n} \Big),\\ P_{n+1} - \sqrt{2} Q_{n+1} &=& \Big( 1 - \sqrt{2} \Big) \Big( P_{n} - \sqrt{2} Q_{n} \Big),\\ \end{eqnarray} $$

and as $P_1=1$ and $Q_1=1$, we obtain

$$ \begin{eqnarray} P_{n} + \sqrt{2} Q_{n} &=& \Big( 1 + \sqrt{2} \Big)^n,\\ P_{n} - \sqrt{2} Q_{n} &=& \Big( 1 - \sqrt{2} \Big)^n, \end{eqnarray} $$

whence

\begin{eqnarray} P_{n} &=& \frac{\Big( 1 + \sqrt{2} \Big)^n + \Big( 1 - \sqrt{2} \Big)^n}{2},\\ Q_{n} &=& \frac{\Big( 1 + \sqrt{2} \Big)^n - \Big( 1 - \sqrt{2} \Big)^n}{2\sqrt{2}}, \end{eqnarray}

therefore

$$ a_n = \frac{\Big( 1 + \sqrt{2} \Big)^n + \Big( 1 - \sqrt{2} \Big)^n} {\Big( 1 + \sqrt{2} \Big)^n - \Big( 1 - \sqrt{2} \Big)^n} \sqrt{2}. $$

Note that

$$ \begin{eqnarray} a_1 &=& \frac{\Big( 1 + \sqrt{2} \Big) + \Big( 1 - \sqrt{2} \Big)} {\Big( 1 + \sqrt{2} \Big) - \Big( 1 - \sqrt{2} \Big)} \sqrt{2} = 1,\\ a_2 &=& \frac{\Big( 1 + \sqrt{2} \Big)^2 + \Big( 1 - \sqrt{2} \Big)^2} {\Big( 1 + \sqrt{2} \Big)^2 - \Big( 1 - \sqrt{2} \Big)^2} \sqrt{2} = \frac{3}{2},\\ a_3 &=& \frac{\Big( 1 + \sqrt{2} \Big)^3 + \Big( 1 - \sqrt{2} \Big)^3} {\Big( 1 + \sqrt{2} \Big)^3 - \Big( 1 - \sqrt{2} \Big)^3} \sqrt{2} = \frac{7}{5},\\ \vdots \end{eqnarray} $$

And we obtain

$$ \begin{eqnarray} \lim_{n \rightarrow \infty} a_n &=& \lim_{n \rightarrow \infty} \frac{\Big( 1 + \sqrt{2} \Big)^n + \Big( 1 - \sqrt{2} \Big)^n} {\Big( 1 + \sqrt{2} \Big)^n - \Big( 1 - \sqrt{2} \Big)^n} \sqrt{2}\\ &=& \lim_{n \rightarrow \infty} \frac{ 1 + \Big( \displaystyle \frac{1 - \sqrt{2}}{1 + \sqrt{2}} \Big)^n} {\ 1 - \Big( \displaystyle \frac{1 - \sqrt{2}}{1 + \sqrt{2}} \Big)^n} \sqrt{2}\\ &=& \sqrt{2} \end{eqnarray} $$