3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – John Martin Apr 15 '16 at 19:16
  • $\begingroup$ Would you please elaborate on that ? $\endgroup$ – Noob101 Apr 15 '16 at 19:16
  • 2
    $\begingroup$ 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. $\endgroup$ – Logan M Apr 15 '16 at 19:27
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Did Apr 15 '16 at 20:22
  • 1
    $\begingroup$ @Bungo increasing function. $\endgroup$ – Did Apr 15 '16 at 21:18
3
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Noob101 Apr 15 '16 at 20:04
  • $\begingroup$ @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. $\endgroup$ – Bungo Apr 15 '16 at 20:11
  • $\begingroup$ "So without further information, we cannot determine whether $x_n$ converges or diverges." - as I show in my answer, this is actually not true. $\endgroup$ – mathguy Apr 15 '16 at 20:12
  • $\begingroup$ @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. $\endgroup$ – Bungo Apr 15 '16 at 20:14
  • $\begingroup$ 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. $\endgroup$ – mathguy Apr 15 '16 at 20:15
0
$\begingroup$

(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!

$\endgroup$
  • $\begingroup$ I just edited the question , I had forgot to mention that c lies in the open interval (0,1) $\endgroup$ – Noob101 Apr 15 '16 at 19:18
  • $\begingroup$ Apologies for the late edit @Barry Cipra $\endgroup$ – Noob101 Apr 15 '16 at 19:24
  • $\begingroup$ 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) $\endgroup$ – Zach466920 Apr 15 '16 at 19:28
  • $\begingroup$ @SuryakantShrivastava, no problem. I only added the note so it wouldn't look like I hadn't read the problem carefully. $\endgroup$ – Barry Cipra Apr 15 '16 at 19:29
  • $\begingroup$ @Zach466920, I wasn't annoyed, I was just adding a note to warn readers that the answer no longer answered the question. $\endgroup$ – Barry Cipra Apr 15 '16 at 19:33
0
$\begingroup$

@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).

See http://mathworld.wolfram.com/LogisticMap.html

or https://en.wikipedia.org/wiki/Logistic_map

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

$\endgroup$
-2
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Noob101 Apr 15 '16 at 19:24
  • $\begingroup$ 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. $\endgroup$ – John Martin Apr 15 '16 at 19:27
  • $\begingroup$ 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... $\endgroup$ – John Martin Apr 15 '16 at 19:30
  • $\begingroup$ 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 . $\endgroup$ – Noob101 Apr 15 '16 at 20:05
  • $\begingroup$ 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. $\endgroup$ – mathguy Apr 15 '16 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.