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

A: 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.
A: 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.  
