<s>[INST] 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.
 [/INST] 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.
</s>