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.
 A: 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.
A: 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}.$$
A: 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}
$$
A: The function $f(x) = 1+\frac1{1+x}$ is decreasing on $\mathbb{R}^+$; $0\lt a\lt b\implies f(b)\lt f(a)$.  From this you can 'hopscotch' back and forth between odd and even terms: since $a_1\lt a_3$, then $a_2=f(a_1)\gt a_4=f(a_3)$, and therefore $a_3=f(a_2)\lt a_5=f(a_4)$, etc.  Now, consider the two subsequences $b_n = a_{2n}$ and $c_n=a_{2n+1}$.  You've just shown that $b_n$ is decreasing and bounded below (by $1$), so it has a limit $b$. Likewise, $c_n$ is increasing and bounded above (by $2$), so it has a limit $c$.  What's more, by the original definitions of the $b_n$ and $c_n$ sequences you have $f(b) = c$ and $f(c)=b$, so in particular $f(f(b))=b$.  Now, you can write out $f(f(x))$ explicitly, and solve the equation $f(f(x))=x$; you'll find that it simplifies out to a quadratic equation in $x$, and only one of its roots is in the range $1\leq x\leq 2$.  Since both $b$ and $c$ are solutions of this equation, they must in fact be this positive root.  Since they're both the same, your original sequence $a$ has the same root as its limit as well.
A: You can use Pell number in your proof (two steps):
1)Show that $\displaystyle a_n=\frac{P_{n}+P_{n-1}}{P_{n}}$.
2)Solve reccurence $P_{0}=0$, $P_{1}=1$, $P_{n}=2P_{n-1}+P_{n-2}$ to find direct formula for $P_{n}$.
Both steps you can do for example by induction.
A: Set $b_n = a_n + 1$.
$b_n$ now defines the covergents of the continued fraction $$2 + \cfrac{1}{2 + \cfrac{1}{2+\dots}}$$
So, convergence, irrationality, alternate subsequences monotonicity etc etc all are shown in one shot.
A: Can you show that $a_{2n}$ is decreasing and $a_{2n-1}$ is increasing? Because if so, and they converge to the same thing (say $L$), you have the answer. You have the subsequence $a_1, a_3, a_5,\cdots$ converges and $a_2, a_4, a_6,\cdots$ converges. Hence for all $\varepsilon>0$ there exists $N>0$ such that if $n>N$ then $|a_n-L|<\varepsilon$.
A: Most inelegant method I guess:
$a_{n+2}=1+\cfrac{1}{1+a_{n+1}}=1+\cfrac{1}{1+1+\cfrac{1}{1+a_n}}=1+\cfrac{1+a_n}{3+2a_n}
$
So $a_{n+2}-a_n=2\cfrac{2-a_n^2}{3+2a_n}$
Clearly from definition $a_n>1$
Also if $a_n>\sqrt{2}$ then $a_{n+2}>1+\cfrac{1+\sqrt{2}}{3+2}=\cfrac{6}{5}+\cfrac{\sqrt{2}}{5}>\cfrac{4\sqrt{2}}{5}+\cfrac{\sqrt{2}}{5}=\sqrt{2}$
if $a_n<\sqrt{2}$ then $a_{n+2}<1+\cfrac{1+1}{3+2\sqrt{2}}=1+\cfrac{2(3-2\sqrt{2})}{9-8}=7-4\sqrt{2}=5\times\cfrac{7}{5}-4\sqrt{2}<5\times \sqrt{2}-4\sqrt{2}=\sqrt{2}$
Now $a_1=1<\sqrt{2}$, $a_2=1.5>\sqrt{2}$ So by induction, the sequences $a_1,a_3,a_5,\ldots$ and $a_2,a_4,\ldots$ are monotone increasing/decreasing respectively, and is bounded above/below by $\sqrt{2}$. These two sequences clearly converges to the same limit, and so $(a_n)$ converges to the common limit which is $\sqrt{2}$  (so in fact $\sqrt{2}$ is supremum and infimum of the sequences)
A: A quick way to show convergence and identify the limit is to notice that the sequence is $$\{1,1+\cfrac{1}{2},1+\cfrac{1}{2+\cfrac{1}{2}},1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2}}},\cdots \}$$ which is the continued fraction for $\sqrt2.$
