# Use the contraction principle to prove that $a_{n+1}=1+1/a_n$ converges.

So I need to prove that $a_{n+1}=1+1/a_n$, $a_1=1$ converges by the contraction principle.

That means $|a_{n+2}-a_{n+1}|\le k|a_{n+1}-a_n|$ holds for any $n$, for a certain $0<k<1$.

Now this question is very closely related to another question of mine.

Now I've tried proving this by writing all terms out: $|1+1/a_{n+1}-1-1/a_{n}|=|1/a_{n+1}-1/a_{n}|=|\frac{a_{n+1}-a_{n}}{a_{n+1}a_n}|$
Now basically if I could find a $k$, such that $k\ge\frac{1}{a_{n+1}a_n}$, for any $n$, I'd be done (I think).

Now since the sequence seems to go as follows: $a_1=1$, $a_2=2$, $a_3=3/2$, $a_4=5/3$ $a_5=8/5$, it seems logical that any $a_ia_j\ge a_1a_3=3/2$ for for $i$$\ne$$j$. (I)

Therefore any $\frac{1}{a_{n+1}a_n}\le2/3$. In that case if we pick $k=2/3$, we have $|\frac{a_{n+1}-a_{n}}{a_{n+1}a_n}|\le\frac{2}{3}|a_{n+1}-a_n|=k|a_{n+1}-a_n|$.

Now my problem is that I don't know
(a) how to prove the assumption I made at (I), I mean, how do I prove that there's no $1<a_n<3/2$? (Clearly any term is greater than $1$.)
(b) whether my overall reasoning is correct,
(c) if there's a much easier way to solve this.

Now I found a similar exercise, which I'm having just as much trouble with (these recursive sequences are hard to grasp), the exercise is as follows:

$a_{n+2}=\frac{a_{n+1}+a_n}{2}$, with $a_1$, $a_2$ being any two real numbers. Prove by the contraction principle that this sequence diverges. Now writing these terms out doesn't get me anywhere, I feel.

$|a_{n+2}-a_{n+1}|=|\frac{a_{n+1}+a_n}{2}-\frac{a_{n}+a_n-1}{2}|=|\frac{a_{n+1}-a_{n-1}}{2}|$ but this isn't really helping. Perhaps
$|a_{n+2}-a_{n+1}|=|\frac{a_{n+1}+a_n}{2}-a_{n+1}|=|\frac{a_{n}-a_{n+1}}{2}|\le\frac{1}{2}|a_{n+1}-a_{n}|$

All right, I guess I solved my second question there. But I'll leave the scratchwork/solution there so that other people can learn from it if they wish. Anyways my first question still holds,

$f(x)=1+\frac1x$ maps $[\frac32,2]$ into itself, you almost had that written down: \begin{align} \frac32&\le x\le 2\\ \implies \frac12&\le \frac1x\le \frac23\\ \implies \frac32&\le f(x)\le \frac53<2 \end{align} and thus for $x,y\in[\frac32,2]$ $$|f(y)-f(x)|=\frac{|y-x|}{xy}\le\frac49\,|y-x|$$
You could also show by induction that $$a_{n+k}=\frac{F_{k}+F_{k+1}a_n}{F_{k-1}+F_{k}a_n}$$ where the $F_k$ are the Fibonacci numbers with $F_{-1}=1,F_0=0,F_1=1$.
• Good! It is easy to prove $a_n \in [3/2. 2]$ – S. Y Nov 21 '16 at 3:55
First, note that $$f(x) = 1 + 1/x.$$ $$a_{n} = f(a_{n-1}).$$ A limit will require $$x= f(x).$$
Now$$f'(x) = -1/x^2.$$ So provided you can show $a_n \geq c >1,$ then $|f'|$ is bounded below 1. The MVT then establishes a contraction mapping.