Study convergence of $x_{n+1} = \frac{1}{2x_n - 1}$ when $x_1 = {9\over 10}$

Question

Given a recurrence relation $$ x_{n+1} = \frac{1}{2x_n - 1}\\ x_1 = {9\over 10}\\ n\in\Bbb N $$ Figure out whether the sequence converges and find $\lim x_n$ in case it exists.

I've started with finding a fixed point of the recurrence, namely: $$ L = \frac{1}{2L -1} \iff 2L^2-L -1 = 0 \iff (L-1)\left(L+{1\over 2}\right) = 0 $$

The only possible finite limits are $\left\{1, -{1\over 2}\right\}$.

Then I proceeded with calculating a few first terms: $$ x_n = \left\{{9\over 10}, {5\over 4}, {2\over 3}, 3, {1\over 5}, -{5\over 3}, -{3\over 13}, \cdots \right\} $$

Using induction suppose that: $$ \forall n\ge6:x_n \le 0 $$

We have: $$ x_n < 0 \implies 2x_n < 0\implies 2x_n - 1 < 0 \implies \underbrace{{1\over 2x_n -1}}_{x_{n+1}} < 0 $$

So it follows that indeed all terms after $6$-th are less than $0$. And we are left with only one possible value for the limit, namely $L = -{1\over 2}$.

At this point I got into troubles. The problem is that according to the graph the sequence is bouncing around its limit point.

A reasonable step would be to prove that $x_{2n}$ is monotonically increasing while $x_{2n-1}$ is monotonically decreasing and both are bounded by $-{1\over 2}$ above and below accordingly, but I failed to do that. Is there a simple way to prove monotonicity? If not what steps should I take to finish the study of the sequence?

I was thinking about induction, but then I have to "jump" over odd and even indices for $x_{2n}$ and $x_{2n-1}$, not sure whether that's applicable. The equations for odd and even terms are as follows: $$ x_{2n} = \frac{2x_{2n-2}-1}{3-2x_{2n-2}}\\ x_{2n-1} = \frac{2x_{2n-3}-1}{3-2x_{2n-3}} $$

What I want to prove eventually is: $$ x_{2n-2} \le x_{2n} \le -{1\over 2} \\ x_{2n-1} \ge x_{2n-3} \ge -{1\over 2} $$

Please note that this question is from limits section. Even though it describes some kind of a dynamic system I would like to keep away from that part of Math since I'm not familiar with it, and use concepts understandable by pre-calc/calc 1 student.

Answer 1

If $f(x) = 1/(2 x - 1)$ we have $$ \frac{f(x) + 1/2}{x + 1/2} = \frac{1}{2x-1} $$ Now $$ \left| \frac{1}{2x-1} \right| < 1 \ \text{if}\ x < 0$$ Thus as soon as you get negative values of $x_n$, $|x_n + 1/2|$ decreases in each iteration. Moreover, as you mentioned, the $x_n$ stay negative. Therefore $\lim_{n \to \infty} |x_n + 1/2|$ must be $0$, i.e. $\lim_{n \to \infty} x_n = -1/2$.

Answer 2

Hint: Plot $\dfrac{2x-1}{3-2x}$ and see that it is increasing. Prove it.

Answer 3

Try $$x_n=-\frac{56+(-2)^n}{2(-28+(-2)^n)}$$

Answer 4

Here's a useful result that we can use. Suppose that we have a sequence created by a function $f$ where

$$x_{n+1}=f(x_n)$$

(in this case, $f(x)=\frac{1}{2x-1}$.) If $x^*$ is a fixed point (so $f(x^*)=x^*$), $f'$ is continuous, and $|f'(x^*)|<1$, then there exists an open interval containing $x^*$ such that the sequence converges to $x^*$ if it starts in this interval. More generally, we look for the largest interval containing $x^*$ whose derivative is less than $1$, and the theorem still holds. Our derivative is

$$f'(x)=-\frac{2}{(2x-1)^2},\;\;\;\;f'(-1/2)=-1/2,\;\;\;\;f'\left(\frac{1-\sqrt{2}}{2}\right)=-1$$

Thus, if the sequence is eventually smaller than $(1-\sqrt{2})/2$ but larger than $-1/2$, then the sequence converges to $-1/2$.

Answer 5

We can even find the explicit form of the general term. The sequence is given by applying a Möbius transformation via the matrix $A$ below: $$ A = \begin{bmatrix} 0&1\\2&-1 \end{bmatrix} = \underbrace{ \begin{bmatrix} 1 & 1\\1 & -2 \end{bmatrix}}_T \underbrace{ \begin{bmatrix} 1 &\\&-2 \end{bmatrix}}_D \underbrace{ \begin{bmatrix} 1 & 1\\1 & -2 \end{bmatrix}^{-1}}_{T^{-1}} \qquad\ , $$ where in general a matrix with entries $a,b,c,d$ acts on a $z$ as $z\to(az+b)/(cz+d)$. Now $A^n=TD^nT^{-1}$, which gives a formula for $A^n$, so $$ A^n\cdot\begin{bmatrix}9/10\\1\end{bmatrix} = \frac 1{30} \begin{bmatrix} -(-2)^n + 28\\ 2\cdot(-2)^n + 28 \end{bmatrix} \ , $$ so $$ x_{n+1}= \frac{-(-2)^n + 28}{2\cdot(-2)^n + 28} \to-\frac 12\ . $$

---

sage check:

sage: A = matrix(QQ, 2, 2, [0,1,2,-1])
sage: D, T = M.jordan_form(transformation=1)
sage: D
[ 1| 0]
[--+--]
[ 0|-2]
sage: T
[ 1  1]
[ 1 -2]
sage: var('n');
sage: A^n*vector([9/10, 1])
(-1/30*(-2)^n + 14/15, 1/15*(-2)^n + 14/15)
sage: a(n) = (-(-2)^n + 28)/(2*(-2)^n + 28)
sage: for n in [0..10]:
....:     print "x(%s) = %s" % (n+1, a(n))
....:     
x(1) = 9/10
x(2) = 5/4
x(3) = 2/3
x(4) = 3
x(5) = 1/5
x(6) = -5/3
x(7) = -3/13
x(8) = -13/19
x(9) = -19/45
x(10) = -45/83
x(11) = -83/173