proving convergence for a sequence defined recursively

The sequence $\left \{ a_{n} \right \}$ is defined by the following recurrence relation: $$a_{0}=1$$ and $$a_{n}=1+\frac{1}{1+a_{n-1}}$$ for all $n\geq 1$

Part 1)- Prove that $a_{n}\geq 1$ for all $n\geq 0$ Part2)- Prove that the sequence $\left \{ a_{n} \right \}$ converges to some real number $x$, and then calculate $x$

For the first part, I could prove it using induction. For the second part: The problem is how to prove that this sequence is convergent. Once the convergence is proved, then from the recurrence relation we can deduce that $x=\sqrt{2}$. In order to prove it is convergent, I tried to see how this sequence converges to $x$. I calculated the terms $a_{0}$, $a_{1}$, $a_{2}$, $a_{3}$, $a_{4}$. I can see that the sequence is neither decreasing nor increasing, so the monotone convergence theorem cannot be applied. I can see that the distance between two consecutive terms is getting smaller and smaller, so I tried to prove that this sequence is contractive. $\left | a_{n+1} -a_{n}\right |=\frac{1}{\left | 1-a_{n} \right |\left | 1+a_{n} \right |}\left | a_{n}-a_{n-1} \right |$, and obviously, $\frac{1}{\left | 1+a_{n} \right |}\leq \frac{1}{2}$. I need to prove that $\frac{1}{\left | 1-a_{n} \right |}\leq \alpha$ where $0< \frac{\alpha }{2}< 1$, and hence the sequence is contractive and therefore it is convergent. If you have any idea how to prove $\frac{1}{\left | 1-a_{n} \right |}\leq \alpha$ or any other idea please share...

-
See Proving the continued fraction representation of $\sqrt{2}$. (And perhaps also the questions linked to that one.) –  Martin Sleziak Jul 19 '12 at 17:25

Hint: Find $c$ such that $$\frac{a_{n+1}-\sqrt2}{a_{n+1}+\sqrt2}=c\,\frac{a_{n}-\sqrt2}{a_{n}+\sqrt2}.$$

-
I found that $c=\frac{1-\sqrt{2}}{1+\sqrt{2}}< 1$, but I couldn't figure out how to use your hint to prove the convergence of the sequence. Can you elaborate please? –  C. Lambda Jul 19 '12 at 19:37
Surely you know the asymptotics of $(x_n)$ when $x_{n+1}=cx_n$. Which very much depends on whether $|c|\lt1$ or $|c|\gt1$. Be careful though that here $c\lt1$ is irrelevant since $c\lt0$. However... –  Did Jul 19 '12 at 20:43
Thanks for the hint. So, you're defining: $x_{n}=\frac{a_{n}-\sqrt{2}}{a_{n}+\sqrt{2}}$. Then: $x_{n+1}=cx_{n}=...=c^{n+1}x_{0}$. It follows then that: $\lim_{n \to \infty }\left | x_{n+1} \right |=\lim_{n \to \infty }\left | c \right |^{n+1} \left | x_{0} \right |=0$ because $\left | c \right |< 1$. From the definition of $x_{n}$, we conclude that: $a_{n}=\sqrt{2}\frac{1+x_{n}}{1-x_{n}}$, and it follows that $(a_{n})$ is convergent because it is a quotient of two convergent sequences, and $\lim_{n \to \infty }a_{n}=\sqrt{2}$. I hope I didn't miss anything –  C. Lambda Jul 19 '12 at 20:59
Seems good to me. Well done. –  Did Jul 20 '12 at 8:09

The function $\displaystyle f(x) = 1 + \frac{1}{1+x}$ has derivative $\displaystyle f'(x) = - \frac{1}{(1+x)^2}.$ On $[1,\infty)$ we have $-1/4 \leq f'(x) <0$ so the sequence converges by the Contraction Mapping Theorem.

-

This answer shows that if $b$ and $d$ have the same sign, then $$\frac{a+c}{b+d}\text{ is between }\frac{a}{b}\text{ and }\frac{c}{d}$$ Therefore, $$a_{n+1}=\frac{a_n+2}{a_n+1}\tag{1}$$ is between $1$ and $2$.

Furthermore, \begin{align} a_{n+1}^2-2 &=\left(\frac{a_n+2}{a_n+1}\right)^2-2\\ &=\frac{2-a_n^2}{(a_n+1)^2}\tag{2} \end{align} Therefore, induction and $(2)$ show that $$0\le(-1)^n(2-a_n^2)\le\frac1{4^n}\tag{3}$$ Thus, $(3)$ shows that $$\lim_{n\to\infty}a_n=\sqrt{2}\tag{4}$$

-
Nice trick! I like this one –  C. Lambda Jul 19 '12 at 20:33

You already have found out that the limit point would have to be $\sqrt{2}$. We have to make use of this knowledge. The simplest way is to replace the given sequence $(a_n)_{n\geq0}$ by the new sequence $$b_n:=a_n-\sqrt{2}\qquad(n\geq0)\ .$$ Now we have to prove $\lim_{n\to\infty}b_n=0$ which (if true) is certainly simpler than proving convergence to an unknown number $\xi$.

One has $b_0=1-\sqrt{2}\doteq-0.414$, and an easy computation shows that the $b_n$ obey the following recursion: $$b_n={1-\sqrt{2}\over 1+\sqrt{2}+b_{n-1}}\ b_{n-1}\ .$$ Note the factor $b_{n-1}$ on the right. If we can show that the fraction in front of it is $<1$ in absolute value we are done. As the $b_{n-1}$ appears also in this fraction we have to be a little careful. I leave it to you to prove the following assertion:

For all $n\geq0$, if $|b_{n-1}|\leq1$, then $$|b_n|\leq{\sqrt{2}-1\over\sqrt{2}}\ |b_{n-1}|<1\ .$$

-
What a beautiful proof! Thanks for sharing –  C. Lambda Jul 19 '12 at 20:32