<s>[INST] 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.
 [/INST] 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}
$$
</s>