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

• How would you subtract the fractions $$\frac1{2+a_n} - \frac1{2+a_{n+1}}?$$ – Thomas Andrews Feb 5 '15 at 2:45
• What happens when you write the difference as one fraction? – Johanna Feb 5 '15 at 2:46
• The recurrence is supposed to be $a_{n+1}=\frac1{2+a_n}$, right? – Math1000 Feb 5 '15 at 2:50
• Have you been asked to prove it using a specific way? – science Feb 5 '15 at 2:54
• @science no, just prove it's convergent, but was given the hint of using induction to prove that the inequality holds in this case. Also, induction's a weak point for me as I don't have much experience in it until recently. After obtaining a common denominator under the absolute value I'm not sure how to proceed to prove what I'm looking for – Jonathan Wu Feb 5 '15 at 2:55

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

To prove the sequence is convergent using the inequality

$$|a_{n+1}-a_n| < \frac{1}{2^n}$$

you need the fact which states that "if $\sum_{n} |a_{n+1}-a_n|< \infty$ then the sequence $a_n$ is Cauchy" which implies the sequence is convergent.

• I'm not sure I've gotten that far yet, I haven't seen that sum before. I've only recently been introduced to Cauchy sequences – Jonathan Wu Feb 5 '15 at 3:16