10
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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$... $\endgroup$ Jul 10 '14 at 2:47
8
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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]$. $\endgroup$
    – Ian
    Jul 10 '14 at 2:17
  • $\begingroup$ He did say he showed $1 \leq a_n \leq 2$ already but I agree still that is worth pointing out. $\endgroup$
    – Zarrax
    Jul 10 '14 at 2:27
  • $\begingroup$ 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$. $\endgroup$ Jul 10 '14 at 7:02
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ian
    Jul 10 '14 at 2:31
  • $\begingroup$ But I wanted to prevent that, by simply showing the simple recursion in the form as I used it... $\endgroup$ Jul 10 '14 at 2:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ian
    Jul 10 '14 at 2:42
  • $\begingroup$ @Ian: There you have a point... Perhaps I should have mentioned matrices, eigenvalues and eigenvectors... Thanks for the advice!!! $\endgroup$ Jul 10 '14 at 2:44
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ inversive is decreasing? $\endgroup$ Jul 10 '14 at 0:00
  • $\begingroup$ @AsdrubalBeltran Yes, that would be a better word for it. :-) $\endgroup$ Jul 10 '14 at 0:02
  • $\begingroup$ Thank you, but I how show that $b_n\downarrow$ and that $c_n\uparrow$? $\endgroup$ Jul 10 '14 at 15:48
  • $\begingroup$ @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. $\endgroup$ Jul 10 '14 at 17:15
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Yes this is my idea, but this difficult to me. $\endgroup$ Jul 9 '14 at 23:52
  • $\begingroup$ The 2 subsequences need to converge to the same thing $\endgroup$
    – JonHerman
    Jul 10 '14 at 0:05
  • $\begingroup$ Yes @Balla in My case $\lim a_{2n}=\lim a_{2n-1}$ $\endgroup$ Jul 10 '14 at 0:07
  • $\begingroup$ 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. $\endgroup$
    – JonHerman
    Jul 10 '14 at 0:14
1
$\begingroup$

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)

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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