The Gateway to Computer Science Excellence
+16 votes

Consider the sequence $\langle x_n \rangle , \: n \geq 0$ defined by the recurrence relation $x_{n+1} = c . x^2_n -2$, where $c > 0$.

Suppose there exists a non-empty, open interval $(a, b)$ such that for all $x_0$ satisfying $a < x_0 < b$, the sequence converges to a limit. The sequence converges to the value?

  1. $\frac{1+\sqrt{1+8c}}{2c}$
  2. $\frac{1-\sqrt{1+8c}}{2c}$
  3. $2$
  4. $\frac{2}{2c-1}$
in Combinatory by Boss (16.3k points)
retagged by | 1.5k views
please someone answer it!!

I am getting option B using hit and trial.

Let c = 1, x_0 = 1


\\x_1 \,\,\,= c \cdot x_0^2 - 2\\\\ \indent= 1(1)^2-2\\ \indent = -1\\\\ x_2 \,\,\,= c \cdot x_1^2 - 2\\\\ \indent= 1(-1)^2 - 2\\ \indent = -1

So, the value converges to -1, which is equal to \frac{1-\sqrt{1+8\times 1}}{2\times 1}

Which means that B is correct.


Since it converges, we can write:

x=cx^2 -2


cx^2 -x -2 = 0

Solving for x:

x=\frac{1\pm \sqrt{1+8c}}{2c}

So both A) and B) can be the values.

Take $x_0 = 2$, then it con.verges to $2$
It also converges to 2

Convergence, in mathematics, property (exhibited by certain infinite series and functions) of approaching a limit more and more closely as an argument (variable) of the function increases or decreases or as the number of terms of the series increases. For example, the function y = 1/x converges to zero as x increases.


4 Answers

+13 votes
Best answer
Lets take a look when $c=1$

The value the recurrence converges to must be,  $\dfrac{1\pm\sqrt{1+8\times1}}{2\times 1} =2,{-1} $

However, when we take the positive square root, i.e. when $x_{i}$ supposedly converges to $\dfrac{1+\sqrt{1+8c}}{2c}$,

the convergence does not hold for the neighborhood.

$\quad x_{i}=\lim\limits_{\delta \to 0} 2+\delta$

$x_{i+1}=1\times x^{2}_{i}-2=\lim\limits_{\delta \to 0}\left(2+\delta\right)^{2}-2$

$\qquad=\lim\limits_{\delta \to 0} 4-2+\delta ^{2}+4\delta$

$x_{i+1}=\lim\limits_{\delta \to 0} 2+\delta ^{2}+4\delta$

We can see that $x_{i+1}$ is further than $x_{i}$ from the assumed convergence value of $\lim\limits_{i \to \infty} x_{i}=2$

Similarly, the value does not converge when $x_{i}$ approaches $2$ from the left side of the number line.

When the negative square root is considered, the convergence does hold for neighbors on either side.

$\quad x_{i}=\lim\limits_{\delta \to 0} \left({-1}\right)+\delta$

$x_{i+1}=1\times x^{2}_{i}-2=\lim\limits_{\delta \to 0} \left(\left({-1}\right) +\delta\right)^{2}-2$

$\qquad =\lim\limits_{\delta \to 0} 1-2+\delta ^{2}-2 \delta$

$x_{i+1}=\lim\limits_{\delta \to 0} -1+\delta^{2}-2\delta$


$\quad x_{i}=\lim\limits_{\delta \to 0} \left({-1}\right)-\delta$

$x_{i+1}=1\times x^{2}_{i}-2=\lim\limits_{\delta \to 0} \left(\left({-1}\right) -\delta\right)^{2}-2$

$\qquad =\lim\limits_{\delta \to 0} 1-2+\delta ^{2}+2 \delta$

$x_{i+1}=\lim\limits_{\delta \to 0} -1+\delta^{2}+2\delta$

Hence, when negative square root is considered, the value oscillates around the convergence point, and actually converges.

Therefore the answer should be only B.
by Boss (22.8k points)
selected by

When you're going for higher order terms such as \delta ^{2}, \delta ^{4} etc with the condition \delta\rightarrow 0 the values are actually diminishing. 0.1 > 0.1^2 > 0.1^4 and so on. And all these values become 0. What you may want to look at maybe is \delta \rightarrow 0^{+} or \delta \rightarrow 0^{-}.

Secondly, convergence can happen from one side only. For converging to a value, lets say x=c, why is it necessary that the iteration should converge for x=c+\delta and x=c-\delta where \delta \rightarrow 0 at the same time? Only one of them can hold true for convergence.


Ignore the higher order terms, and notice that when x_i = \lim_{\delta\to 0}{2+\delta}x_{i+1} = \lim_{\delta\to 0}{2+\underbrace{4\delta}_{>\delta} +\underbrace{\delta^2}_0}

For example when x_i = 2.000001, x_{i+1} > 2.000004, x_{i+2} > 2.000016 \ldots

So, the value does not converge.

I had to show that the value does not converge from either side when the positive square root is taken, hence I proved them both.

I think you're right. I also saw this behaviour. Oscillating value around -1 starting with -0.9999 and diverging value near 2.00001 So only -1 seems to be the right value. Changing it now.

But at -1.0 also the value seems to diverge, though oscillate:x_{1}=-1.000199, x_{2}=-0.999599, x_{3}=-1.000799, x_{4}=-0.998399

what is the meaning of converges??
+17 votes

A sequence converges means at some point $x_{n+1} = x_{n}$


$x=cx^2 -2$


$cx^2 -x -2 = 0$

Solving for $x$:

$x=\frac{1\pm \sqrt{1+8c}}{2c}$

So both (A) and (B) can be the values.

by Junior (873 points)
edited by
How can a sequence converge to $2$ values ??

It should be only $1$
Since it converges, we can write:


can anyone explain how can we write this???
Sir, what will be the final answer both a and b or only b?
I think the answer is only B.
You are solving according to praggy sir solutions?
+7 votes


$x_{n+1} = cx_{n}^{2}-2 , c > 0$

For stability, We can write non-linear first order recurrence as :- $x_{n} = f(x_{n-1})$ (or) $x_{n+1} = f(x_{n})$

So, $x_{n+1} = cx_{n}^{2}-2 , c > 0$  becomes $x_{n} = cx_{n}^{2}-2 , c > 0$ (or) For simplicity, to find fixed stable points , we can write it as :- $x = cx^{2}-2 , c > 0$

Now, after solving the given equation , we will get :-

$x= \frac{1\pm \sqrt{1+8c}}{2c}$

Now, here we have $2$ fixed points $x_{1}= \frac{1 + \sqrt{1+8c}}{2c}$ and $x_{2}= \frac{1 - \sqrt{1+8c}}{2c}$

Now, We have to check that for which fixed point the given recurrence converges.

As we know if $f' < 0$ at a point or slope is negative then it means function $f$ is  strictly decreasing and if $f' > 0$ then it means function $f$ is strictly increasing.

 So, if we find $f' < 0$ in a given interval , it means function $f$ is decreasing or converses to a fixed point in the given interval.

So, Now, Since here , $f(x) = cx^{2} - x -2$

So, $f'(x) = 2cx - 1$


$f'(x_{1}) = 2c * \left ( \frac{1+\sqrt{1+8c}}{2c} \right ) - 1$

So, $f'(x_{1}) \nless 0 , c> 0$


$f'(x_{2}) = 2c * \left ( \frac{1-\sqrt{1+8c}}{2c} \right ) - 1$

So, $f'(x_{2}) < 0 , c> 0$

So, here local stable point is $\frac{1-\sqrt{1+8c}}{2c}$ for which given recurrence converges.

So, Answer is (B)

Reference :-

by Boss (17k points)
It's the best answer containing all the purely mathematical statements. I think this should be selected as the best answer.
+3 votes

Let c = 1, x_0 = 1


\\x_1 \,\,\,= c \cdot x_0^2 - 2\\\\ \indent= 1(1)^2-2\\ \indent = -1\\\\ x_2 \,\,\,= c \cdot x_1^2 - 2\\\\ \indent= 1(-1)^2 - 2\\ \indent = -1

So, the value converges to -1, which is equal to \frac{1-\sqrt{1+8\times 1}}{2\times 1}

exactly , only B will be the answer. as all the term of X converges to -1

by Active (4.8k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,258 answers
104,737 users