Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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...

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer

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} $$

share|cite|improve this answer
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\ .$$

share|cite|improve this answer
What a beautiful proof! Thanks for sharing – C. Lambda Jul 19 '12 at 20:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.