Nested roots sequence, how to prove it's monotone and bounded? Let $a\ge1$ and define the sequence $(x_n)$ recursively by: $$x_1 = \sqrt{a}$$ $$x_{n+1}= \sqrt{a+x_n}$$
Here's what I did:
Plugging in some values makes it seem as if the sequence is increasing. I first solve the equation $t=\sqrt{a+t}$, equivalently $t^2 -t -a =0$, to get an idea what's going on. The roots are $$t_{1,2}= \frac{1 \pm \sqrt{1+4a} }{2}.$$ Therefore, between the roots, that is for $$t\in \left( \frac{1 - \sqrt{1+4a} }{2}, \frac{1 + \sqrt{1+4a} }{2}\right)$$
we have $t^2-t-a \le 0 \iff t \le \sqrt{a+t}$. Here's my attempt at showing inductively that $$\forall n\in \mathbb{N}, \ x_n \le \frac{1 + \sqrt{1+4a} }{2}$$
For $n=1$, the statement is true (simple arithmetic). Suppose it's true for $n$. Consider
$$x_{n+1}= \sqrt{a+x_n}\le \sqrt{a+\frac{1 + \sqrt{1+4a} }{2}}=\frac{1 + \sqrt{1+4a} }{2},$$
because $\frac{1 + \sqrt{1+4a} }{2}$ satisfies $x=\sqrt{x+a}$.
So this establishes the sequence $(x_n)$ is bounded. Now, by induction again, I try to show it's monotonically increasing. The base case $x_1\le x_2$ is obvious. Assume (strong induction) $x_{n-1}\le x_n$ for all $n>1$. But since we have $$x_1\le x_n \le \frac{1 + \sqrt{1+4a} }{2}, $$ 
then $x_n$ lies in the appropriate interval, so $x_n \le \sqrt{a+x_n}=x_{n+1}.$
Is this proof correct? Can the condition on $a$ be relaxed to $a>0$? Maybe even small negative $a$? And could someone provide me with another proof of convergence of $x_n$? I absolutely hate this one!
 A: Bounded and monotoneis probably the best way to show it, though one can take different steps do show this.
For example for monotnicity: $$x_{n-1}<x_n\implies a+x_{n-1}<a+x_n\implies \sqrt{a+x_{n-1}}<\sqrt{a+x_{n}}\implies x_{n+1}<x_n.$$
Indeed, we still have a strictly increasing bounded sequence if $a>0$. 
With $a=0$ the sequence is of course constant (and thus converging). With $a<0$, $x_1$ is undefined.
An alternatiuve method might be to investigate $y_n:=\frac{1+\sqrt {4a}}2-x_n$ and show that it decreases by looking at $\frac{y_{n+1}}{y_n} $.
By the way, you didn' specify wether it was part of the problem statement to actually compute $\lim_{n\to\infty} x_n$, but I guess you know how to handle that last step.
A: Here is another proof of convergence. Note that, $$|x_{n+2}-x_{n+1}|=|\sqrt{a+x_{n+1}}-\sqrt{a+x_{n}}|=\frac{|x_{n+1}-x_n|}{|\sqrt{a+x_{n+1}}+\sqrt{a+x_{n}}|}=\frac{1}{C} |x_{n+1}-x_n|$$  Where $C:=|\sqrt{a+x_{n+1}}+\sqrt{a+x_{n}}|\geq 2$, since $a\geq 1$ and $x_n\geq 0$ (Using induction). Hence $1/C\leq 1/2<1$ and so the sequence is contractive. Now this implies that the sequence is Cauchy and hence convergent.
