How do I prove the sequence $x_{n+1}=\sqrt{\alpha +x_n}$, with $x_0=\sqrt \alpha$ converges? ( boundedness?)

I need to "study the limit behavior of the following sequence" and then compute the limit. I can compute the limit and prove the monotonicity, but I am having trouble proving boundedness. I tried to understand from other similar posts how this could be done, but since I didn't understand I'm asking it as a new question. The sequence is $x_{n+1}=\sqrt{\alpha +x_n}, x_0=\sqrt \alpha, \alpha>0$.

It seems to be monotonically increasing.

Proof:

It can be shown by induction that the sequence is monotonically increasing.

Claim that $x_{n+1}\geq x_n$ $$x_1=\sqrt{\alpha+\sqrt\alpha}>\sqrt\alpha=x_0$$ $x_{n+1}\implies x_{n+2}$ $$x_{n+1}=\sqrt{\alpha+x_n}<\sqrt{\alpha+x_{n+1}}=\sqrt{\alpha+\sqrt{\alpha+\sqrt\alpha}}=x_{n+2}$$ Boundedness:

Because the sequence is monotonically increasing and $x_o=\sqrt\alpha$, it is bounded below by $\sqrt\alpha$. Now comes the part where I have to prove that the sequence is bounded above. The problem is that I don't know how to start, so if anyone could give me a bit of a push I'd be grateful.

The limit:

I know that $\lim\ x_n=\lim \ x_{n+1}$, so letting $\lim\ x_n=x$ then $$x=\sqrt{\alpha+x}$$ and solving would give $x=\frac{1+\sqrt{1+4\alpha}}{2}$.

May somebody please confirm my proof thus far, and help me prove the upper bound? Thanks!

Solution 1:

Instead of just proving the boundedness, let me show you the logic to construct the proof.

Step 1 guess the answer.

In this step, you don't need to be rigorous. You just use whatever intuition to guide you for a potential candidate of answer.

Let's say you want an upper bound $L$.

What does it mean? It means you want an $L$ such that for any $x \in (0,L]$, $\sqrt{\alpha+x} \le L$.

Since $\sqrt{\alpha+x}$ is an increasing function in $x$, you want

$$\begin{align}&\sqrt{\alpha+L} \le L\\ \iff &\alpha + L \le L^2\\ \iff &\alpha \le L^2 - L\\ \iff &\alpha + \frac14 \le (L - \frac12)^2\\ \implies &\sqrt{\alpha + \frac14} + \frac12 \le L\tag{*} \end{align}$$ Notice $\sqrt{\alpha + \frac14}$ is bounded above by $\sqrt{\alpha} + \sqrt{\frac14} = \sqrt{\alpha} + \frac12$. This means if you have chosen $L$ such that $\sqrt{\alpha} + 1 \le L$, $(*)$ will be satisfied.

Step 2 verify you answer.

Once you have a potential candidate for an answer, you need to verify it. If your logic of finding the candidate is reasonable. You can usually reverse the steps to prove it is indeed what you want.

Let $L = \sqrt{\alpha}+1$, for any $0 \le x \le L$, we have:

$$\sqrt{\alpha + x} \le \sqrt{\alpha + L} = \sqrt{\alpha+ \sqrt{\alpha}+1} < \sqrt{\alpha + 2\sqrt{\alpha}+1} = \sqrt{\alpha} + 1 = L$$

This means if you start with a $x_n \le L$, you will get $x_{n+1} = \sqrt{\alpha + x_{n}} \le L$.

Since $x_0 \le L$, the boundedness of all $x_n$ is proved.

BTW, the rest of your steps look fine.

Solution 2:

Let denote by $f(x)=\sqrt{x+\alpha}$ and $x_f=\frac{1+\sqrt{1+4\alpha}}{2}$ the fixed point of $f$ i.e. we have $f(x_f)=x_f$. It's clear that $f$ is montonically increasing so the sequence $(x_n)$ is also increasing. Moreover since $x_0=\sqrt{\alpha}<x_f$ and with $x_{n+1}=f(x_n)<f(x_f)=x_f$ by simple induction we prove that $(x_n)$ is bounded above by $x_f$ then the sequence $(x_n)$ is convergent. Now we can conclude.

Solution 3:

We want to prove that there is an upper bound. This is probably much easier to do if we have a numerical idea of what might work. Certainly if $\alpha$ is huge, then the terms of our sequence will be pretty big.

Let's calculate. It is more informative to do it without a calculator. Suppose that $\alpha \lt 100$. Then $x_0\lt 10$, so $x_1\lt \sqrt{100+10}\lt 11$, so $x_2\lt \sqrt{100+11}\lt 11$, so $x_3\lt 11$, and so on.

Thus if $\alpha\lt 100$, we have found an upper bound for the $x_k$, namely $11$.

What about if $\alpha$ is real big? Like a bit below $10000$? Calculate. We get $x_0\lt 100$, $x_1\lt \sqrt{10000+100}\lt 101$, and then all the rest are less than $101$.

OK, time to get formal. Suppose that $\alpha \lt 10^{2a}$, where $a$ is an integer $\ge 1$. We show by induction on $n$ that $x_n \lt 10^a+1$ for all $n$.

We have $x_0\lt 10^a \lt 10^a+1$. Suppose that for a certain integer $k$, we have $x_k\lt 10^a+1$. Then $$x_{+1}=\sqrt{\alpha +x_k}\lt \sqrt{10^{2a}+10^a+1}\lt 10^a+1.$$ (The fact that $\sqrt{10^{2a}+10^a+1}\lt 10^a+1$ is easily verified by squaring.)

Remark: Now that we have a full proof, we could elegantize, if that's a word. But note that the game was basically over once we did the crude computation for the case $\alpha\lt 100$.

In this problem, the limit, if it exists, satisfies a simple quadratic equation, and we "know" a tight bound. It is technically straightforward to verify by induction that the number is indeed an upper bound. But the crude approach we took can be quite useful when the algebra is less simple.

Solution 4:

1) Informally: draw the graphs of $f(x)=\sqrt{\alpha+x}$ and $g(x)=x$ simultaneously. The intersection is the unique fixed point of $f$, that is $x_\infty=\frac{1+\sqrt{1+4\alpha}}{2}$. The derivative of $f$ at $x_\infty$ is positive and smaller than $1$. This is an attractive fixed point. But there is more. To figure out what is going on, pick $x_0$ and follow the orbit $x_n=f^{\circ n}(x_0)$ on the graphs, as it bounces from the graph of $f$ to the graph of $g$. The behaviour is obvious.

Here is an example, with $\alpha=2$, starting from $x_0=4$. Orange->Black->Green->Red->Blue is the beginning of the orbit. More precisely: $x_0$ is the abscissa of the Orange point, $x_1$ that of the Green point, $x_2$ the one of the Blue point. Can you see how to continue? Project alternately onto the graph of $f$ and the graph of $g$.

2) Formally:

If $x_0<x_\infty$, then $x_n$ is increasing and bounded above by $x_f$. You can prove it by induction. All you have to observe is that $f([-\alpha,x_\infty))\subseteq [-\alpha,x_\infty))$ and that $f(x)>x$ on this interval.

If $x_0>x_\infty$, then $x_n$ is decreasing and bounded below by $x_\infty$. Proof by induction again, given that $f((x_\infty,+\infty))\subseteq (x_\infty, +\infty)$ and that $f(x)<x$ on this interval.

In both cases, $x_n$ converges as it is bounded and monotonic. Hence it converges to the unique fixed point $x_\infty$.