<s>[INST] Showing a sequence defined recursively is convergent Given the recursively defined sequence
$$ a_1 = 0, a_{n+1} = \frac 1{2+a^n} $$
Show it converges. I'm working with Cauchy sequences, and proved in a previous question that any sequence of real numbers $(a_n)$ satisfying: 
$$|a_n - a_{n+1}| \leq \frac1{2^n} $$
is convergent (by showing $(a_n)$ was Cauchy), and was told that it may be helpful to use induction to prove that the above recursive sequence satisfies the inequality and is therefore convergent.
Work:
Base Case: When $n = 1 , a_1 = 0, a_2 = \frac12,$ so $$ \left|0-\frac12\right| \leq \frac1{2^{1}}$$ and the base case checks out
Inductive Step: Want to show $$|a_{n+1} - a_{n+2}| \leq \frac1{2^{n+1}} $$
So $$\left|\frac1{2+a_n} - \frac1{2+a_{n+1}}\right| \leq \frac1{2^{n+1}}$$
And I'm not sure where to proceed from here. Any help would be greatly appreciated, thanks.
 [/INST] Continuing as Thomas Andrews suggested,
$a_{n+1}-a_{n+2}
=\frac1{2+a_n}-\frac1{2+a_{n+1}}
=\frac{(2+a_{n+1})-(2+a_n)}{(2+a_n)(2+a_{n+1})}
=\frac{a_{n+1}-a_n}{(2+a_n)(2+a_{n+1})}
$
so
$|a_{n+1}-a_{n+2}|
=\big|\frac{a_{n+1}-a_n}{(2+a_n)(2+a_{n+1})}\big|
<|\frac{a_{n+1}-a_n}{4}|
$.
From this,
$|a_{n+k}-a_{n+k+1}|
<|\frac{a_{n+1}-a_n}{4^k}|
$.
Putting
$n = 0$,
$|a_{k}-a_{k+1}|
<|\frac{a_{1}-a_0}{4^k}|
$
which is more than enough
to get convergence.
It is interesting
that this shows that
the convergence is at least
$\frac1{4^k}$,
not just
$\frac1{2^k}$.
To find the limit:
$|a_{n+1}-a_{n}|
=|a_n-\frac1{2+a_n}|
=|\frac{a_n(2+a_n)-1}{2+a_n}|
=|\frac{a^2_n+2a_n-1}{2+a_n}|
=|\frac{(a_n+1)^2-2}{2+a_n}|
$.
Since $a_n$ converges,
$(a_n+1)^2-2
\to 0
$
or
$a_n \to \sqrt{2}-1$.
To find the true rate of convergence,
since
$a_n \to \sqrt{2}-1$,
$|a_{n+1}-a_{n+2}|
=\big|\frac{a_{n+1}-a_n}{(2+a_n)(2+a_{n+1})}\big|
\approx \big|\frac{a_{n+1}-a_n}{(2+\sqrt{2}-1)(2+\sqrt{2}-1)}\big| 
= \big|\frac{a_{n+1}-a_n}{(\sqrt{2}+1)^2)}\big| 
= \big|\frac{a_{n+1}-a_n}{3+\sqrt{2}}\big| 
$,
so the convergence
is like
$\frac1{(3+\sqrt{2})^k}
$.
</s>