# Cauchy sequence $x_n=\sqrt{a+x_{n-1}}$

I have to show that this sequence $$x_n=\sqrt{a+x_{n-1}} \hbox{ with } x_1=\sqrt{a}$$ is a Cauchy sequence for every $a>0$. I have done the following calculations: $$\left| x_{n+2}-x_{n+1} \right|=\left| \sqrt{a+x_{n+1}}-x_{n+1}\right|=\left|\frac{a+x_{n+1}-x_{n+1}^2}{\sqrt{a+x_{n+1}}+x_{n+1}} \right|= \left|\frac{x_{n+1}-x_n}{\sqrt{a+x_{n+1}}+x_{n+1}}\right|$$ I don't come up with a boundary for the denominator so that $$\left|\frac{x_{n+1}-x_n}{\sqrt{a+x_{n+1}}+x_{n+1}}\right|<k\cdot\left|x_{n+1}-x_n\right| \hbox{ with } k<1$$ Any hint? I know I can use induction to easily prove that the sequence is convergent, but I'd like to prove it's Cauchy without using convergence. Thank you in advance.

• Just an idea - wouldn't it make sense to square both sides of the first equation and use $$x_n^2-a=x_{n-1}$$ to show the convergence? – Yuriy S Jun 9 '16 at 14:00
• But you wrote $a>0$, it doesn't converge otherwise and $x_1$ becomes complex – Yuriy S Jun 9 '16 at 14:37

In order to prove that your sequence is a Cauchy sequence it is probably easier to prove that $$\sqrt{a},\;\sqrt{a+\sqrt{a}},\;\sqrt{a+\sqrt{a+\sqrt{a}}},\;\ldots$$ is a convergent sequence. The candidate limit is the positive solution of $x^2-x=a$, namely $\frac{1+\sqrt{1+4a}}{2}>\sqrt{a}$. Your sequence is trivially increasing, so you just need to show it is bounded.
We have: $$\sqrt{a}<\frac{1+\sqrt{1+4a}}{2}$$ and the function $f(x)=\sqrt{a+x}$ is increasing over $\mathbb{R}^+$, hence by applying $f$ to both sides, $$\sqrt{a+\sqrt{a}} < \frac{1+\sqrt{1+4a}}{2}$$ follows, and by induction it follows that $x_n<\frac{1+\sqrt{1+4a}}{2}$ holds for any $n\in\mathbb{N}$. On the other hand, $$L=\lim_{n\to +\infty} x_n = \sup_{n\geq 1}x_n$$ has to fulfill $L^2-L=a$. That proves:

$$\forall a>0,\quad \sqrt{a+\sqrt{a+\sqrt{a+\sqrt{a+\ldots}}}} = \frac{1+\sqrt{1+4a}}{2}.$$

• Yes, I know I can use induction to show convergence but I'd like not to use convergence. Only a proper boundary. Thanks anyway. – Claudio Jun 9 '16 at 14:52

Claim. The given sequence is bounded from above by $$\frac{1 + \sqrt{4a + 1}}{2} = \alpha$$

Proof. We proceed by induction. For $k = 1$ we have that

$$\sqrt{a} = \frac{2\sqrt{a}}{2} = \frac{\sqrt{4a}}{2} < \frac{1 + \sqrt{4a + 1}}{2}$$

Now, assuming that the statement is true for $k = n$, we have

$$x_{n+1} = \sqrt{a + x_n} < \sqrt{ \frac{1 + 2a + \sqrt{4a + 1}}{2} }$$

Observe that

$$\left( \frac{1 + \sqrt{4a + 1}}{2} \right)^2 = \frac{4a + 2 + 2\sqrt{4a + 1}}{4} = \frac{1 + 2a + \sqrt{4a + 1}}{2}$$

which establishes the bound for $x_{n+1}$.

Now, we prove that the sequence is monotone increasing. For this, the following inequality is crucial:

Claim. For $0 \leq x < \alpha$, we have that $x < \sqrt{a+x}$.

Proof. The given inequality is true precisely when $x^2 - x - a < 0$. The inequality factors as $(x - \alpha)(x - \alpha') < 0$ where $\alpha' < 0$, therefore the second factor is always positive when $x \geq 0$, and the first factor is negative precisely when $x < \alpha$.

Now, since we have $0 \leq x_k < \alpha$ for all $k$, it follows by this claim that

$$x_{k+1} = \sqrt{a + x_k} > x_k$$

Since the sequence $x_k$ is monotone increasing and bounded from above, by the monotone convergence theorem it is convergent; and thus Cauchy.

You could use another way $$x_{n+2}-x_{n+1}={x_{n+1}-x_n\over x_{n+2}+x_{n+1}}$$ As $x_n>0\;\forall n$, the above relation shows that your sequence is monotone.

$x_{n+1}<\sqrt{a}+1+\sqrt[2^n]a$

Proof: Let's name the above statement $P(n)$. For positive numbers $x,y$ we have $$\sqrt{x+y}<\sqrt x+\sqrt y$$ $x_1=\sqrt{a}<\sqrt{a}+1+a=\sqrt{a}+1+\sqrt[2^0]{a}$. Suppose $P(n)$ is true. $$x_{n+2}=\sqrt{a+x_{n+1}}<\sqrt{a+\sqrt a+1+\sqrt[2^n]{a}}<\sqrt{(\sqrt a+ 1)^2+\sqrt[2^n]{a}}<\sqrt a+1+\sqrt[2^{n+1}]a$$ We complete our proof using induction.

As $$\lim_{n\to\infty}\sqrt[2^{n}]a=1,\\ \exists m: n>m\implies x_{n}<\sqrt a+2$$ Therefore your sequence is bounded above by $\max(x_1,x_2,...,x_m,\sqrt a+2)$ and below by $\sqrt a$. As every bounded monotone sequence is convergent and every convergent sequence in $\mathbb{R}$ (or a complete metric space) is a Cauchy sequence, your sequence is Cauchy.