6
$\begingroup$

Let $\{a_n\}$ be defined by $a_1 =1 $ and $a_{n+1} = 1 + {\dfrac{1}{a_n}}$ with $n \in N$.

Show that $a_{n+1}= 1 + {\dfrac{1}{a_n}}$ converges.

I know the limit but how can I show that is a Cauchy sequence or that this sequence converges.

$\endgroup$

marked as duplicate by Michael Lee, Rolf Hoyer, Misha Lavrov, Krish, JonMark Perry Nov 23 '17 at 8:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

7
$\begingroup$

Hint. Let $f(x)=1+1/x$ then $f:[3/2,2]\to [3/2,2]$ and for $x\in [3/2,2]$, $$|f(x)-f(y)|= \left|\frac{1}{x}-\frac{1}{y}\right|\leq \frac{4}{9}|x-y|.$$ That is $f$ is a contraction.

Now $a_{n+1}=f(a_n)$ and $a_2=f(a_1)=2$ and by the Banach fixed-point theorem, $(a_n)_n$ tends to the unique fixed point of $f$ in the interval $[3/2,2]$.

$\endgroup$
  • $\begingroup$ ¸Nice one +1.... $\endgroup$ – Aqua Nov 15 '17 at 16:30
6
$\begingroup$

After so many good answers, this one is just for knowledge sharing $$a_1=1, a_2=2, a_3=\frac{3}{2}, a_4=\frac{5}{3}, ...$$ and by induction $$a_n=\frac{F_{n+1}}{F_n}$$ where $\{F_n\}$ are Fibonacci numbers, since $$a_{n+1}=1+\frac{1}{a_n}=1+\frac{F_n}{F_{n+1}}=\frac{F_{n+1}+F_{n}}{F_{n+1}}=\frac{F_{n+2}}{F_{n+1}}$$ and $$\lim\limits_{n\rightarrow \infty}\frac{F_{n+1}}{F_{n}}=\varphi=\frac{1+\sqrt{5}}{2}$$

$\endgroup$
  • 1
    $\begingroup$ Nice one +1......... $\endgroup$ – Aqua Nov 15 '17 at 16:30
2
$\begingroup$

Hint: Show that if $a_n < \frac{1 + \sqrt{5}}{2}$ then $a_n < a_{n+2}$. Similarly, show that if $a_n > \frac{1+\sqrt{5}}{2}$, then $a_n > a_{n+2}$.

$\endgroup$
2
$\begingroup$

So let the limit - assuming there is one - be $a$ and note that $2\gt a\gt 1$ and that $a=1+\frac 1a$ whence $a^2=a+1$.

Now write $a_n=a+e_n$ so that $$a+e_{n+1}=1+\frac 1{a+e_n}$$

On clearing fractions we get $$a^2+ae_{n+1}+ae_n+e_ne_{n+1}=a+e_n+1$$ so that $$e_{n+1}=e_n\cdot\frac {1-a}{a+e_n}=-e_n\cdot\frac {a-1}{a+e_n}$$

Use this to show that the error term alternates in sign and decreases in absolute value - you should be able to show that the error reduces geometrically in magnitude, and therefore tends to zero. If the error tends to zero, you have convergence.

This technique of isolating the error may not be the most efficient, but if you are stuck, it can help to show what is going on. Note that all the terms equivalent to the original equation conveniently drop out - this is quite a general phenomenon, and if it doesn't happen, it's an indication either that there is no limit, or that there has been a mistake in calculation.

$\endgroup$
  • $\begingroup$ Thank you very much! I showed that $|e_n| \geq |e_{n+1}|$, hence $|e_n|$ is falling monotonously and limited so |e_n| is converged, but why $ \rightarrow e_n$ is converged ? $\endgroup$ – Anna Saabel Nov 14 '17 at 20:14
  • 1
    $\begingroup$ @AnnaSaabel So if, for example, you have a situation where $1.5\lt a \lt 1.7$ and $|e_n|\lt 0.1$ then $|e_{n+1}|\lt \frac {0.7}{1.4} |e_n|$ and the error halves in magnitude each time. So once you are close you get closer very quickly, and the error tends to zero. $\endgroup$ – Mark Bennet Nov 14 '17 at 21:14
  • $\begingroup$ okay, but how can i prove that the error tends to zero ? $\endgroup$ – Anna Saabel Nov 14 '17 at 21:22
  • $\begingroup$ @AnnaSaabel So the series goes $1, \frac 32, \frac 53, \frac 85 =1.6$. The errors alternate in sign, so $\frac 53 -\frac 85=\frac 1{15}$ is bigger than the error ar $\frac 85$ (we added the previous error to it). So the error is already less than $\frac 1{10}$ and the value is in the range I suggested, so the error is halving after that. So $|e_{n+4}|\lt 2^{-n}|e_4|$ which is a constant multiple of $2^{-n}$ and $2^{-n}\to 0$ $\endgroup$ – Mark Bennet Nov 14 '17 at 21:50
1
$\begingroup$

Here is yet another answer: Observe that $a_n \geq 1$ for all $n \in \{1, 2, 3, ...\}$. Let $b=\frac{1}{2}(1+\sqrt{5})$, which satisfies $b = 1+\frac{1}{b}$ and $b>1$. Then for all $n \in \{1, 2, 3, ...\}$: $$ |a_{n+1}-b| = |(1+\frac{1}{a_n}) - (1 + \frac{1}{b})| = \frac{|a_n-b|}{a_nb} \leq \frac{|a_n-b|}{b}$$ where the last inequality uses $a_n\geq 1$. The error decreases exponentially fast.

$\endgroup$
  • $\begingroup$ It seems this is similar to the Robert Z answer, except I am comparing directly with the limiting point $b$ rather than proving a general contraction property for a function $f(x)$ over a certain interval. $\endgroup$ – Michael Nov 14 '17 at 20:17
0
$\begingroup$

As Marcus M said, first $a_{n+2}=\frac{2a_n+1}{a_n+1}$ showing those properties. Then show $\{a_{2n}\}$ and $\{a_{2n+1}\}$ really convergent to that value.

E.g. for $\{a_{2n}\}$, because of the fact that $f(x)=\frac{2x+1}{x+1}$ is strictly increasing and $x>f(x)$ when $x>\frac{\sqrt{5}+1}{2}:=g$. Assume the limit (infimum) is $x^*>g$, for all $x\geqslant x^*$. If There are always points from $[x^*,x^*+\delta)$. If $\exists\hat{x}, f(\hat{x})\leq x^*$, then $f(f(\hat{x}))=f(x^*)<x^*$ contradict to

$\endgroup$
0
$\begingroup$

Let $f(x) = 1+{1\over x}$. We have $f([1,2]) \subset [1,2]$. Since $f(1) = 2 > 1$ and $f(2) = {3 \over 2} < 2$ we see that $f$ has a fixed point in $[1,2]$.

Note that $\phi(x) = f(f(x)) = {2x+1 \over x+1}$ satisfies $0 \le \phi'(x) \le {1 \over 4}$ for $x \in [1,2]$ hence has a unique (in $[1,2]$) fixed point $x^*$ and hence $x_{2n+1} \to x^*$ for some $x^* \in [1,2]$. Note that any fixed point of $f$ is a fixed point of $\phi$, hence $x^*$ is the fixed point of $f$ and it follows that $x_{2n+2} = f(x_{2n+1})$ converges to $x^*$ as well.

$\endgroup$

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