# Does the sequence $x_{n+1} = \frac{1}{2} ( (x_n)^2 + c )$ diverge?

Does this recursive sequence defined by the relation

$x_{n+1} = \frac{1}{2} ( (x_n)^2 + c )$

diverge. Given that we know that , $x_0 > 1$ and c lies in the open interval (0,1)

If yes then please how ? If not then also please proof.

My attempt : My initial attempt was to assume that the sequence diverges , given that it is strictly increasing. However, I realised that I could not actually proof that the series is going towards infinity. ( After one of my friends said that just saying that the series is monotonically increasing won't be enough )

So far my attempt to prove that the sequence goes to infinity has been to find the general term , and then show that as n tends to infinity the function also tends to infinity. However i could not find the general term .

So I tried another approach too , which was basically trying to find a sequence $b_n$such that each term of the new sequence is smaller than the corresponding term of the original sequence {$a_n$} and then to show that $b_n$ diverges .

However, I haven't found such a sequence yet !.

Any help on whether I am proceeding in the right direction , and proof of whether the sequence converges or diverges will be appreciated.

• try computing $\lim_{n\to\infty}\frac{x_n}{x_{n+1}}$ in two different ways, assuming that $\lim_{n\to\infty}x_n = L$. If this is too vague, let me know and I can post an answer with a more extended hint. – John Martin Apr 15 '16 at 19:16
• Would you please elaborate on that ? – Noob101 Apr 15 '16 at 19:16
• The sequence is not necessarily strictly increasing as you claim. Consider $x_0 = \frac32$ and $c= \frac14$, then $x_1 = \frac{11}8 < \frac32$. For these initial conditions the sequence is strictly decreasing and bounded below by 0, so it is convergent. – Logan M Apr 15 '16 at 19:27
• A qualitative analysis of the sequence fully solves this... To wit, note that the function $u:x\mapsto\frac12(x^2+c)$ is increasing on $x\geqslant0$, such that $u(x)>x$ for $x<a_c$ and $x>b_c$ and such that $u(x)<x$ for $a_c<x<b_c$, with $0<a_c<b_c$ the fixed points of $u$. These remarks, and these alone, show that $x_n\to a_c$ for every $x_0<b_c$, $x_n\to b_c$ if $x_0=b_c$ and $x_n\to\infty$ if $x_0>b_c$. Now, if $x_0>1$, three cases remain: $1<x_0<b_c$, $x=b_c$, and $x>b_c$, with $b_c=1+\sqrt{1-c}$ and $a_c=1-\sqrt{1-c}$. – Did Apr 15 '16 at 20:22
• @Bungo increasing function. – Did Apr 15 '16 at 21:18

Let $a = x_0$; then the answer depends on $a$ AND $c$.

Let $t_1 = 1 - \sqrt{1-c}$ and $t_2 = 1 + \sqrt{1-c}$ be the roots of the quadratic equation $x = \frac 1 2 (x^2 + c)$.

If $a = t_1$ or $a = t_2$ then $x_1 = a = x_0$ and by induction the sequence is CONSTANT and therefore it converges to $a$ (which, recall, is either $1 - \sqrt{1-c}$ or $1 + \sqrt{1-c}$).

If $a > t_2$ then $x_1 = \frac 1 2 (a^2 + c) > a = x_0$, and by induction the sequence is strictly increasing. It then must have limit $+\infty$; if it was bounded, it would have limit $L$ where $L$ must be either $t_1$ or $t_2$, which is not possible because all the terms are $\ge a > t_2$.

If $0 \le a < t_1$, then on the one hand $x_1 = \frac 1 2 (a^2+c) >a = x_0$, and on the other hand $x_1 < t_1$: $x_1 < t_1 \iff a^2 + c < 2(1-\sqrt{1-c})$ which results directly, by substitution, from $a < t_1 = 1 - \sqrt{1-c}$. So in this case, by induction, we have $x_{n+1} > x_n$ while still $x_{n+1} < t_1$. The sequence is strictly increasing and bounded by $t_1$. Since the limit in this case exists and must equal either $t_1$ or $t_2$, we find that the sequence converges to $t_1$.

This leaves the case $a = x_0$ strictly between $t_1$ and $t_2$. With a similar argument (exercise!), the sequence in this case is strictly DECREASING while all the values are still strictly between $t_1$ and $t_2.$ Conclusion: the sequence is convergent and the limit must be $t_1$.

BONUS: If $c=1$, this argument shows that $x_n \to 1$ if $0 \le x_0 \le 1$ and diverges to $+\infty$ if $x_0 > 1$. If $c > 1$ then the sequence is strictly increasing to $+\infty$ regardless of $x_0$.

If the sequence converges to some limit $L$, then we must have $$L = \frac{1}{2}(L^2 + c)$$ so $$L^2 - 2L = -c$$ Completing the square on the left hand side, this becomes $$(L - 1)^2 = 1-c$$ and therefore $$L = 1 \pm\sqrt{1-c} <2$$ where the inequality holds because $0 < c < 1$.

Now consider $x_0 = 3$ and $c=1/2$. If $x_n \geq 3$ then $$x_{n+1} = \frac{1}{2}\left(x_n^2 + \frac{1}{2}\right) \geq \frac{1}{2}\left(3^2 + \frac{1}{2}\right)= \frac{19}{4} \geq 3$$ so by induction we see that $x_n \geq 3$ for all $n$. Thus the sequence cannot converge to a limit smaller than $3$. But as shown above, if it does converge to a limit $L$, then $L < 2$. This means that the sequence diverges.

On the other hand, as pointed out by Logan Maingi in the comments, if $x_0 = 3/2$ and $c = 1/4$, then $x_n$ is strictly decreasing and bounded below by $0$, so it converges.

So, if all we know is that $x_0 > 1$ and $c \in (0,1)$, that is insufficient information to decide whether $x_n$ converges or diverges. It depends on the specific values of $x_0$ and $c$, and this dependence is shown precisely in the answer by mathguy.

• Even if the limit exists , then by our method we are getting two different limits (considering both the positive and negative signs of the root) , which itself is a contradiction as we all know that a particular sequence can have only one limit. – Noob101 Apr 15 '16 at 20:04
• @SuryakantShrivastava No, $L = 1 \pm \sqrt{1-c}$ doesn't mean there are two limits, it just means that if there is a limit, it must be one of these two values. – Bungo Apr 15 '16 at 20:11
• "So without further information, we cannot determine whether $x_n$ converges or diverges." - as I show in my answer, this is actually not true. – mathguy Apr 15 '16 at 20:12
• @mathguy I meant, without knowing the specific values of $x_0$ and $c$. If all we know is that $x_0 > 1$ and $c \in (0,1)$, then that is not enough to determine convergence or divergence. I will edit to make this clearer. – Bungo Apr 15 '16 at 20:14
• The proper way to understand the question, though, is to make it dependent of the "free parameters" which are $c$ AND $x_0$! And as you can see, "$x_0 > 1$" is bogus; in my answer I used $x_0 \ge 0$ but not even that is really needed, as $x_1 \ge 0$ anyway. – mathguy Apr 15 '16 at 20:15

(Note: This answer was posted prior to the OP's edit adding the condition $0\lt c\lt1$.)

If $c=0$ and $x_0=2$, the sequence definitely does not diverge!

• I just edited the question , I had forgot to mention that c lies in the open interval (0,1) – Noob101 Apr 15 '16 at 19:18
• Apologies for the late edit @Barry Cipra – Noob101 Apr 15 '16 at 19:24
• Don't add a qualification, you're allowed to be annoyed if the OP changes the constraints on the question. However, it's really your fault for writing a glorified comment. This is because it's perfectly acceptable to change a question after a comment. (-1) – Zach466920 Apr 15 '16 at 19:28
• @SuryakantShrivastava, no problem. I only added the note so it wouldn't look like I hadn't read the problem carefully. – Barry Cipra Apr 15 '16 at 19:29
• @Zach466920, I wasn't annoyed, I was just adding a note to warn readers that the answer no longer answered the question. – Barry Cipra Apr 15 '16 at 19:33

@mathguy @bungo

I post this as an answer but it is only a possible track of answer, of a different type, addressing the problem's intrinsic subtilities.

The structure of the recurrence relationship ($x_{n+1}$ expressed as a quadratic expression of $x_n$ and a parameter $c$) has made me remember to the classical logistic map

$$x_{n+1}=c x_n(1-x_n)$$

with its associated Feigenbaum diagram (chaotic behavior).

My question is: could this problem be treated as - or even shown more or less equivalent to - the logistic map problem ?

Let $L = \lim_{n\to\infty}x_n$. Then $\lim_{n\to\infty}x_{n+1} = L$ as well. Therefore we have $$1 =\lim_{n\to\infty}\frac{x_n}{x_{n+1}} = \lim_{n\to\infty}\frac{x_n}{\frac{1}{2}((x_n)^2 +c)} = \frac{L}{\frac{1}{2}(L^2 + c)}$$

You should be able to solve for $L$, the solution will depend on $c$.

• But what about the case in which the sequence does not converge to a limit , in that case would it be fine to use your method ? @JohnMartin – Noob101 Apr 15 '16 at 19:24
• I am just using $L$ as a place holder in a way, to make the algebra easier. You should end up with some expression like $L = 1 \pm\sqrt{1 - c}$, so $L$ will only be a real number when $1 - c\geq 0$, that is when $c \leq 1$. This method will tell you precisely when $L$ is a finite real number. – John Martin Apr 15 '16 at 19:27
• Also note the comment by @LoganMaingi, which uses the monotone convergence theorem (I like his solution better actually). But mine tells you what $L$ is. It's all a matter of taste I suppose... – John Martin Apr 15 '16 at 19:30
• I have a doubt though , this gives me two possible values of L . As we know that a given sequence can only converge to one single limit . Hence we are arriving at a contradiction . – Noob101 Apr 15 '16 at 20:05
• No, that is the whole point: the equation also has the solution $L = +\infty$, which is the correct answer in some cases. That's really the essence of the problem: decide when the sequence converges and when it diverges. This deserves a de-merit. – mathguy Apr 15 '16 at 20:14