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.
On
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.
On
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$.
On
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.
On
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}.$$
On
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)
On
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} $$
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.