The Gateway to Computer Science Excellence
+14 votes
1.4k 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}$
in Combinatory by Boss (16.3k points)
retagged by | 1.4k views
0
please someone answer it!!
+9

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.

 

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$

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.
by Boss (22.7k points)
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??
+17 votes

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.

by Junior (873 points)
edited by
0
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?
+6 votes

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.

So, Answer is (B)

Reference :- http://www.ms.uky.edu/~droyster/ma114F16/RecursiveSequences.pdf

by Boss (16.4k points)
0
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

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

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,647 questions
56,475 answers
195,396 comments
100,381 users