# GATE2007-IT-76

1.9k views

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

retagged
0
10

I am getting option B using hit and trial.

Let $c = 1, x_0 = 1$

Then,

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

2

Since it converges, we can write:

$x=cx^2 -2$

or

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

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

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.

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$

Also,

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

selected by
0

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.

0

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.

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

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$

2
what is the meaning of converges??

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

Then,

$x=cx^2 -2$

or

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

edited
1
How can a sequence converge to $2$ values ??

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

x=cx^2−2

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

Here,

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

Now,

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

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

Now,

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

0
It's the best answer containing all the purely mathematical statements. I think this should be selected as the best answer.

Let $c = 1, x_0 = 1$

Then,

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

## Related questions

1
2.1k views
Let $H_1, H_2, H_3,$ ... be harmonic numbers. Then, for $n \in Z^+$, $\sum_{j=1}^{n} H_j$ can be expressed as $nH_{n+1} - (n + 1)$ $(n + 1)H_n - n$ $nH_n - n$ $(n + 1) H_{n+1} - (n + 1)$
Consider the $B^{+}$ tree in the adjoining figure, where each node has at most two keys and three links. Now the key $K50$ is deleted from the $B^+$ tree resulting after the two insertions made earlier. Consider the following statements about the $B^+$ tree resulting after ... (i) and (ii) are true Statements (ii) and (iii) are true Statements (iii) and (i) are true All the statements are false
Consider the $B^+$ tree in the adjoining figure, where each node has at most two keys and three links. Keys $K15$ and then $K25$ are inserted into this tree in that order. Exactly how many of the following nodes (disregarding the links) will be present in the tree after the two insertions? $1$ $2$ $3$ $4$
The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. What is the maximum cardinality of the request set, so that the head changes its direction after servicing every request if the total number of tracks are $2048$ and the head can start from any track? $9$ $10$ $11$ $12$