I have a recursive sequence defined by $$a_{n+1}=\frac{1}{a_n+1}$$, where $a_0=7$.
The sequence is bounded, but it's not monotonic. So how does one show, that the sequence converges?
I already found it's limit under the assumption, that it is converging. Which is $a=\frac{\sqrt5-1}{2}$.
Note, that I'm not allowed to use epsilon proofs or proof by induction.
Best Answer
By the recurrence, $$(a_n+1)(a_{n-1}+1)=(\frac{1}{a_{n-1}+1}+1)(a_{n-1}+1)\\=2+a_{n-1}>2$$ since with $a_0=7$ all the terms are obviously positive. Therefore, $$|a_{n+1}-a_n|=\frac{|a_n-a_{n-1}|}{(a_n+1)(a_{n-1}+1)}<\frac12\,|a_n-a_{n-1}|.$$ The rest is a special case of the Banach fixed point theorem: when the distances between consecutive points decrease by a factor less than $1$ the sequence converges (in a complete metric space). As applied to this case, we have by induction: $$|a_{n+1}-a_n|<\frac1{2^n}\,|a_1-a_0|,$$ so the differences decrease at least geometrically. Hence $$|a_{n+m}-a_n|\\\leq (|a_{n+m}-a_{n+m-1}|+\dots+|a_{n+1}-a_n|)\,|a_1-a_0|\\<\left(\frac1{2^{n+m-1}}+\dots+\frac1{2^n}\right)|a_1-a_0|\to0$$ when $n,m\to\infty$ because the geometric series converges. Therefore, $a_n$ is a Cauchy sequence and must converge.