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.

• IF $a_n$ converges you can find the limit also by equating $a_{n+1} = a_n$, whence $\displaystyle a_n = 1 + \frac{1}{a_n+1}$, so $a_n^2=2$... Jul 10 '14 at 2:47

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.

• Technically you need to prove that $f$ maps $[1,2]$ into itself, so that your inequality holds at each step. This is easy, of course: $f$ is decreasing so $f([1,2])$=$[f(2),f(1)]=[4/3,3/2] \subset [1,2]$.
– Ian
Jul 10 '14 at 2:17
• He did say he showed $1 \leq a_n \leq 2$ already but I agree still that is worth pointing out. Jul 10 '14 at 2:27
• I'll add link to Banach fiexd-point theorem, as you have mentioned that this is precisely the sequence from the proof of this theorem when looking for the fixed point fulfilling $f(x)=x$. Jul 10 '14 at 7:02

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

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

• It would be instructive to point out that you are turning the problem into a matrix iteration of the form $\begin{bmatrix} P_{n+1} \\ Q_{n+1} \end{bmatrix} = A \begin{bmatrix} P_n \\ Q_n \end{bmatrix}$ and then diagonalizing $A$. Knowing that, the OP could get some background in linear algebra to see where this idea came from.
– Ian
Jul 10 '14 at 2:31
• But I wanted to prevent that, by simply showing the simple recursion in the form as I used it... Jul 10 '14 at 2:40
• I like the presentation as is. I think it would still be instructive to say "one can view this procedure as a diagonalization argument", because looking at it that way makes it easier to come up with these kinds of arguments in other problems.
– Ian
Jul 10 '14 at 2:42
• @Ian: There you have a point... Perhaps I should have mentioned matrices, eigenvalues and eigenvectors... Thanks for the advice!!! Jul 10 '14 at 2:44

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.

• inversive is decreasing? Jul 10 '14 at 0:00
• @AsdrubalBeltran Yes, that would be a better word for it. :-) Jul 10 '14 at 0:02
• Thank you, but I how show that $b_n\downarrow$ and that $c_n\uparrow$? Jul 10 '14 at 15:48
• @AsdrubalBeltran By their definitions - as I said, $a_1\lt a_3$ implies that $a_2\gt a_4$, and that implies that $a_3\lt a_5$, etc. In terms of the $b$ and $c$ sequences, this means that $c_1\lt c_2$, $b_1\gt b_2$, $c_2\lt c_3$, etc. Jul 10 '14 at 17:15

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.

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.

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

• Yes this is my idea, but this difficult to me. Jul 9 '14 at 23:52
• The 2 subsequences need to converge to the same thing Jul 10 '14 at 0:05
• Yes @Balla in My case $\lim a_{2n}=\lim a_{2n-1}$ Jul 10 '14 at 0:07
• So you want to show that $a_{2k}$ is decreasing. I think this might help: You're trying to show, for even $n$, $a_{n+2}-a_n\leq 0$ this is if and only if $\frac{1}{1+a_{n+1}}-a_n\leq 0$ which is if and only if $\frac{1}{1+\frac{1}{1+a_n}}-a_n\leq 0$ Try simplifying this to get a true inequality which holds if and only if the original one is true. Then handle $a_{2k-1}$ similarly. Jul 10 '14 at 0:14

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)

• I guess that it should be $$a_{n+2} - a_n = 2 \frac{\color{red}{2}-a_n^2}{3+2a_n}$$ Jul 10 '14 at 2:36
• You're right, thanks, I fixed it Jul 10 '14 at 2:41
• Thank you, but not see how show by induction that $a_{2n}\downarrow$ and $a_{2n-1}\uparrow$ Jul 10 '14 at 15:01

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