Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm playing around with a sequence $\{x_n\}$ defined by $$ x_{n+1}=\frac{\alpha+x_n}{1+x_n}=x_n+\frac{\alpha-x_n^2}{1+x_n}. $$ Here $\alpha\gt 1$, and $x_1\gt\sqrt{\alpha}$.

I'm trying to compute $\lim\ x_n$. If it converges, it's easy to compute it as $\sqrt{\alpha}$ from the above equalities, but I don't know if it does or not. Does it?


I made a few observations from the relations (I can included proofs, which are mostly playing with inequalies):

  • $x_n\gt\sqrt{\alpha}\implies x_{n+1}<\sqrt{\alpha}$
  • $x_n\lt\sqrt{\alpha}\implies x_{n+1}>\sqrt{\alpha}$
  • $x_n>\sqrt{\alpha}\implies x_{n+2}<x_n$
  • $x_n<\sqrt{\alpha}\implies x_{n+2}>x_n$

From these I deduced that $x_1>x_3>x_5>\cdots$ and is bounded below by $\sqrt{\alpha}$. Also, $x_2<x_4<x_6<\cdots$ and is bounded above by $\sqrt{\alpha}$. So I know $\{x_{2m}\}$ and $\{x_{2m+1}\}$ both converge.

I figure if $\{x_n\}$ does not converge, then for some $\epsilon>0$, and for any $N$, there exist some $n,m>N$ such that $|x_n-x_m|>\epsilon$, and $n$ and $m$ can be of different parity. Is there some way to get a contradiction? Thanks.

share|improve this question
    
Maybe en.wikipedia.org/wiki/Banach_fixed-point_theorem . –  Potato Dec 31 '11 at 7:25
5  
The simplest, I think, is to compute $x_n$ explicitly. The generalization $$x_{n+1}=\frac{ax_n+b}{cx_n+d}$$ is of the same difficulty level as your problem. The point is that we're iterating a fractional linear transformation. It boils down to computing the $n$ th power of a two by two matrix. The absolute values of the eigenvalues will play a crucial role. –  Pierre-Yves Gaillard Dec 31 '11 at 7:25
    
... Of course, one has to be careful about the possible vanishing of the denominator in $$\frac{ax_n+b}{cx_n+d}\quad.$$ –  Pierre-Yves Gaillard Dec 31 '11 at 7:34
    
Related question: math.stackexchange.com/questions/82479/… and special case for $\alpha=2$: math.stackexchange.com/questions/60325/approximation-to-sqrt2 –  Martin Sleziak Dec 31 '11 at 7:50
    
Thanks @Pierre-YvesGaillard and Potato. –  yunone Dec 31 '11 at 7:51
add comment

3 Answers

up vote 10 down vote accepted

As the comments and the other answers indicate, there are several approaches to this problem; I explain three of them here. Define the functions $f, g : [0, \infty) \to [0, \infty)$ by $$ \begin{align*} f(x) &= \frac{\alpha + x}{1+x}, \\\\ g(x) = f(f(x)) &= \frac{2 \alpha + (1+\alpha)x}{(1+\alpha) + 2x}. \end{align*} $$ In terms of this notation, the sequence satisfies the recurrence $x_{n+1} = f(x_n)$. We need the following two facts about these functions:

  • They are continuous in $[0, \infty)$.
  • Both $f$ and $g$ have a unique fixed-point in $[0, \infty)$, namely $\sqrt{\alpha}$. (Solving the equations also gives an extraneous negative solution that we can discard.)

Method 1.

The OP has already done most of the work by showing that the odd and even subsequences individually converge. To proceed further, we isolate the odd and even terms by writing a recurrence equation for them separately: $$ \begin{align*} x_{2m+1} &= g(x_{2m-1}), \\ x_{2m+2} &= g(x_{2m}) . \end{align*} $$ Since we know that both these subsequences converge, the corresponding limits (possibly the same) satisfy the fixed point equation $x = g(x)$ (thanks to the continuity of $g$). Since this equation has a unique solution $\sqrt{\alpha}$, we conclude that both the odd and even subsequences converge to $\sqrt{\alpha}$, and we are done. $\qquad \diamond$


Method 2.

This is a variation of the previous idea. Again we already know that the odd and even subsequences individually converge; denote the respective limits by $O$ and $E$.

Consider the recurrence equation $x_{n+1} = f(x_n)$; taking limits as $n \to \infty$ through the odd integers, we get $E = f(O)$. Similarly, allowing $n \to \infty$ through the even integers gives $O = f(E)$. To solve these two equations, we simply eliminate $O$ (say), yielding $$E = f(f(E)) = g(E) ,$$ yielding the same equation as in Method 1. (Of course, $O$ satisfies an analogous equation.) Thus, as before, we have the solution $E = O = \sqrt{\alpha}$, and we are done. $\qquad \diamond$


Method 3: Using the Banach fixed-point theorem.

Potato's suggestion of using the Banach fixed-point theorem looks attractive, but unfortunately, it does not apply for this sequence directly. The trouble is that while $f$ does map the complete subspace $[0, \infty)$ into itself, it is not a contraction for $\alpha \geqslant 2$. (Exercise: Check this.)

On the other hand, the iterate $g = f \circ f$ of $f$ is indeed a contraction. To see this, we bound its derivative: $$ \begin{align*} g'(x) &= \frac{(1+\alpha)(1+\alpha+2x) - 2(2\alpha + x(1+\alpha))}{(1+\alpha + 2x)^2} \\ &= \left( \frac{\alpha - 1}{\alpha + 1 + 2x} \right)^2 \\ &\leqslant \left( \frac{\alpha - 1}{\alpha + 1} \right)^2 \lt 1. \end{align*} $$ Now the Banach fixed-point theorem applies for $g$, and says that both

  • $\left(g^{m-1}(x_1) \right) = \left( f^{2m-2}(x_1)\right) = \left(x_{2m-1} \right)$, the odd subsequence of $x_n$; and
  • $\left(g^{m-1}(x_2) \right) = \left( f^{2m-2}(x_2)\right) = \left(x_{2m} \right)$, the even subsequence of $x_n$,

converge to the unique fixed-point of $g$, namely $\sqrt{\alpha}$. Thus the original sequence converges to $\sqrt{\alpha}$ as well. In fact, this method also shows an exponential rate of convergence of $x_n$ to $\sqrt{\alpha}$.

See Keith Conrad's notes for an in-depth explanation of the contraction mapping theorem. Specifically, Theorem 3.1 and Example 3.2 in the notes discuss the case when a function is not a contraction but an iterate of it is. $\qquad \diamond$

share|improve this answer
    
Ah, that makes sense. Thanks Srivatsan. –  yunone Dec 31 '11 at 7:40
1  
Of course not, your answer is yours to edit. Thanks for all the detail, this is a great answer. –  yunone Dec 31 '11 at 18:51
add comment

$$x_{n+1} = 1 + \cfrac{\alpha -1}{1 + x_n} = 1 + \cfrac{\alpha -1}{2 + \cfrac{\alpha -1}{1 + x_{n-1}}} = 1 + \cfrac{\alpha -1}{2 + \cfrac{\alpha -1}{3 + \cfrac{\alpha -1}{1+ x_{n-2}}}} = \cdots $$

Śleszyński–Pringsheim theorem implies that given the continued fraction,

$$b_0 + \cfrac{a_1}{b_1+\cfrac{a_2}{b_2+\cfrac{a_3}{b_3+ \cdots}}}$$

if there exists an $N$ such that $|b_n| \ge |a_n| +1$ for all $n > N$, then the continued fraction converges. In your case $b_n$ is increasing and unbounded while $a_n = \alpha -1$ is a constant. Therefore $x_n$ converges.

share|improve this answer
add comment

Here is a natural generalization. Let $$ A:=\begin{pmatrix}a&b\\ c&d\end{pmatrix} $$ be an invertible real matrix, and let $g$ be the associated fractional linear transformation: $$ gx=\frac{ax+b}{cx+d}\quad. $$ What is natural is to let $g$ acts on the projective line $\mathbb R\cup\{\infty\}$, endowed with the usual topology.

What is the dynamic of the iterations of $g$?

By conjugating $A$, it suffices to consider the cases listed below (corresponding to the possible Jordan forms). In each case, the dynamic is clear. Here is the list:

$\bullet\ \ gx=a\,x, |a| > 1$: the fixed points are $0$, which is repulsive, and $\infty$, which is attractive;

$\bullet\ \ gx=x+1$: the fixed point is $\infty$;

$\bullet\ \ A$ is a rotation by an angle $\theta$. In this case it is better to identify the projective line to a circle in the plane. Then $g$ acts by a rotation of angle $2\theta$.

EDIT A. Here is a consequence of the above observations.

Let $(x_n)_{n\ge0}$ be a sequence of real numbers such that $$ x_{n+1}=\frac{ax_n+b}{cx_n+d} $$ for all $n$, where $$ A:=\begin{pmatrix}a&b\\ c&d\end{pmatrix} $$ is an invertible real matrix. Assume also $x_1\neq x_0$.

Then $(x_n)$ converges in $\mathbb R\cup\{\infty\}$ if and only if the eigenvalues of $A$ are real and the trace of $A$ is nonzero.

This condition is satisfied in your case.

EDIT B. Didier Piau asked very kindly for clarification.

We topologize $X:=\mathbb R\cup\{\infty\}$ by adding to the open sets of $\mathbb R$ the complements (in $X$) of the compact sets of $\mathbb R$. Then $X$ is homeomorphic to a circle.

We define the projective line $Y$ as the set of lines through the origin of $\mathbb R^2$.

We consider the following bijection from $Y$ to $X$: we attach $x/y$ to the line through $(x,y)\neq(0,0)$, with the convention $x/y=\infty$ if $y=0$. We identify $X$ and $Y$ via this bijection.

We let $G'$ be the group of invertible two by two real matrices, which acts (by homeomorhisms) on $Y$ in the obvious way. The kernel of this action is the subgroup of nonzero scalar matrices. We denote the quotient group by $G$, and note that the action of $A$ as above on $X$ is given by $$ Ax=\frac{ax+b}{cx+d}\quad. $$

"Conjugation" means "conjugation in $G$", which is related in a very simple way to conjugation in $G$.

As an example, assume that $A$ is diagonal, i.e. $A=\text{diag}(a,d)$. This gives $$ Ax=\frac{a}{d}\ x. $$ But $A$ is conjugate (in $G'$) to $\text{diag}(d,a)$. This shows that $x\mapsto\lambda x$ is conjugate (in $G$) to $x\mapsto x/\lambda$. This comes down to switching $0$ and $\infty$ by $x\mapsto 1/x$.

Thank you to Didier for his interest!

share|improve this answer
    
Pierre-Yves: I do not find $gx=ax$ with $|a|\lt1$ in your classification. Or is this case conjugate to one of the others? By the way, you might want to explain more precisely the conjugation you consider. –  Did Dec 31 '11 at 11:38
    
Dear @Didier: Thanks! I'll edit the answer. –  Pierre-Yves Gaillard Dec 31 '11 at 12:09
    
Nice edit. Thanks. –  Did Dec 31 '11 at 12:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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