# How do I compute the limit of this sequence $x_{n+1}=\frac{(x_n)^2+b}{2}$, $x_o=0$ and $b\in [0,1]$

I need to study the limit behavior of the sequence and discuss all possible situations with the parameters given. The sequence is $x_{n+1}=\frac{(x_n)^2+b}{2}$, $x_o=0$ and $b\in [0,1]$. This can also be written as $\frac{(x_n)^2}{2}+\frac{b}{2}$. I studied the first few terms to get an idea of the behavior of the sequence, and have a feeling that when $b=0, x_{n+1}=0$ and thus $\lim\ x_n=0$ and when $0<b\leq1, \lim\ x_n=b/2$ because as n gets larger $\frac{(x_n)^2}{2}$ tends to $0$ and $\lim\ (0+\frac{b}{2})=(b/2)$.

Those were my thoughts on the problem, I'm not sure if they are right, but I got stuck trying to prove them.

### Proof of when $b=0, x_{n+1}=0$ for all n, which will imply that $\lim\ x_n=0$:

This can be proved by induction (but I'm not sure how to do it properly):$$x_0=0=0$$$$x_{0+1}=x_1=\frac{0^2+0}{2}=0$$ $x_{n+1}=>x_{n+2}$ $$x_{n+2}=x_{(n+1)+1}=\frac{(x_{n+1})^2+b}{2}=\frac{(x_{n+1})^2}{2}=\frac{0}{2}=0$$ I really don't know if that is how you do the induction. Any help?

### Proof of $0<b\leq1$

When $b=1$, $x_{n+1}=\frac{(x_n)^2+1}{2}=\frac{(x_n)^2}{2}+\frac{1}{2}$. I can't really explain this besides saying that $\frac{(x_n)^2}{2}$ seems to be tending to $0$. Is this correct, and can I have a hint at how to solve it? I'm thinking I may be able to split it into 2 limits, saying $\lim \frac{(x_n)^2}{2}+\lim\ (b/2)=0+(b/2)$.

Thanks for any help!

-
There are many questions on this site discussing such recurrence relations. One of the main ways to find the limit, is to first assume that the limit exists, i.e., $x_n \to L$, and then take the limit of $x_{n+1} = \frac{x_n^2 + b}{2}$ as $n \to \infty$, i.e., $L = \frac{L^2 + b}{2}$. Solving for $L$ then gives you the limit, if it exists. To show that the sequence actually converges and that this is indeed the limit, you could try to show it is monotonically increasing/decreasing and bounded. –  TMM Mar 17 '13 at 0:33
As for mathematical induction, your first step (showing that, for $b=0$, $x_1=0$) is good. Next you want to show that whenever $x_n=0$, then $x_{n+1}=0.$ To do this, assume that, for all $n$, $x_n=0$, then show that this implies that $x_{n+1}=0$. You have done this as well. After you have shown this to be the case you have that $x_1=0$ and that if $x_n=0$, then $x_{n+1}=0$. This means that $x_2=0$, and so on. So you are finished. –  jim Mar 17 '13 at 0:46
You have to show when $b\le 1$, $x_n\le 1$, this ensures you $x_n$ is bounded, then you show that $x_n$ is increasing, if $x_0 = 0$. Then you can see there is a limit $L = (L^2+b)/2$ –  Yimin Mar 17 '13 at 0:49
@jim I read your comment to tried to understand, but I don't know if you are telling me that something is missing/wrong in my induction, or if I have all the parts I need in my induction. May you clarify a little? –  user66807 Mar 17 '13 at 1:05
Your induction is nearly complete. You only need to say something like: Since $x_0=0$, and since $x_{n+1}=0$ whenever $x_n=0$, then, by the principle of mathematical induction, $x_n=0, \forall n.$ The main thing that you were missing in your induction was understanding of what you were essentially doing. I was trying to tell you why your induction works. If you understand this, then you will know how to do it, and know when it is done correctly (in every case). –  jim Mar 17 '13 at 1:49

1. $\{x_n\}$ is monotone increasing:

$x_2\geq x_1.$ Suppose $x_{k+1}\geq x_k$ whenever $1\leq k\leq m~(m\in\mathbb N)$. Consequently, $x_n\geq 0~\forall~ n\leq m.$

$x_{k+2}-x_{k+1}=\dfrac{(x_{k+1})^2-1}{2}-\dfrac{(x_{k})^2-1}{2}=\dfrac{(x_{k+1})^2-(x_k)^2}{2}\geq 0$ whence $\{x_n\}$ is monotone increasing.

2. $\{x_n\}$ is bounded above:

$x_1=\dfrac{b}{2}\leq b.$ Let $x_k\leq b$ for some $m\in\mathbb N.$

Then $x_{k+1}=\dfrac{(x_k)^2+b}{2}\leq b$ (Since $b\in [0,1]$). Thus by induction $b$ is an upper bound of $\{x_n\}.$

By $1$ and $2,$ $\{x_n\}$ converges to some limit $l$ (say). Taking limit as $n\to\infty$ on both sides of $x_{n+1}=\dfrac{(x_n)^2+b}{2}$ we get $l=\dfrac{l^2+b}{2}$ i.e. $l^2-2l+b=0.$ Conseqently $l=1-\sqrt{1-b}$ (Recall $x_n\leq b\implies \lim x_n\leq b\leq 1$).

-
Your "bounded above" induction was really helpful, thanks a lot. I do have a question about your proof that $x_n$ is monotone increasing. Why were you able to say $\dfrac{(x_{k+1})^2-(x_k)^2}{2}\geq 0$? Was is because you stated in the beginning that $x_2\geq x_1$? –  user66807 Mar 17 '13 at 4:52
Glad to be able to help. Note $x_{k+1}\geq x_k$ and both are non-negetive since $0\leq \dfrac{b}{2}= x_1\leq x_2\leq x_3...\leq x_{k+1}$ (by induction hypothesis). That's why $(x_{k+1})^2-({x_k})^2\geq 0.$ –  Sugata Adhya Mar 17 '13 at 5:06
Ah, yes I see it now. Thanks again! –  user66807 Mar 17 '13 at 5:16
You're welcome ! –  Sugata Adhya Mar 17 '13 at 5:17

We deal with positive $b$. First we show by induction that the sequence $\{x_n\}$ is increasing, that is, that $^x_n\lt x_{n+1}$ for all $n$. This is easy to verify for $n=1$.

Suppose it is true for $n=k$. We show it is true for $n=k+1$. So we need to show that $x_{k+1}\lt x^{k+2}$.

From the induction hypothesis $x_k\lt x_{k+1}$ we conclude that $$\frac{x_k^2+b}{2}\lt \frac{x_{k+1}^2+b}{2}.\tag{1}$$ Since $x_{k+1}=\frac{x_k^2+b}{2}$ and $x_{k+2}=\frac{x_{k+1}^2+b}{2}$, the Inequality $(1)$ says precisely that $x_{k+1}\lt x_{k+2}$.

An easy induction shows that the sequence $\{x_n\}$ is bounded above by $1$, and now we can conclude convergence.

The value is the easy part. We have $\lim_{n\to\infty} x_{n}=\lim_{n\to \infty} x_{n+1}$. So if $L$ is their common limit, we have $$L=\frac{L^2+b}{2}.$$ Solve this quadratic for $L$. The root less than $1$ gives $L=1-\sqrt{1-b}$.

-