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.

As part of the programming I do, I recently stumbled
into the sequence $\: \left\langle x_0,x_1,x_2,x_3,... \right\rangle \:$ defined as follows:

$x_{\hspace{0.01 in}0} = 1 \qquad$ and $\qquad$ for all non-negative integers $n$, $\;\;\; x_{\hspace{0.01 in}n+1}\:=\:\frac12 \cdot x_n \cdot (2-x_n)$

I am aware that $\: \left\langle x_0,x_1,x_2,x_3,... \right\rangle \:$ approaches $0$ from the right.
Is there a closed-form expression for $x_{\hspace{0.01 in}n}$?
If no, is there a good closed-form estimate of $x_{\hspace{0.01 in}n}$ for large $n\hspace{0.01 in}$?
(In particular, a better estimate than $0$.)

share|improve this question
I presume you mean $x_n=(1/2)x_{n-1}(2-x_{n-1})$. –  Gerry Myerson Oct 11 '12 at 6:19
Almost. ${}{}\:$ –  Ricky Demer Oct 11 '12 at 16:25
add comment

2 Answers

up vote 2 down vote accepted

Let $a_n=2^{2^n-1}x_n$; then $a_0=1$, and

$$\begin{align*} x_n&=\frac12x_{n-1}(2-x_{n-1})\\ &=\frac12\cdot\frac{a_{n-1}}{2^{2^{n-1}-1}}\left(2-\frac{a_{n-1}}{2^{2^{n-1}-1}}\right)\\ &=\frac{a_{n-1}\left(2^{2^{n-1}}-a_{n-1}\right)}{2^{2^n-1}}\;, \end{align*}$$

so $a_n=a_{n-1}\left(2^{2^{n-1}}-a_{n-1}\right)$. The first few terms of the new sequence are $a_0=1,a_1=1,a_2=3$, $a_3=39$, and $a_4=8463$. OEIS has one match, OEIS A076628, which is described as $2^{2^{n-1}}b_n$, where $b_1=\frac12$ and $b_{n+1}=b_n-b_n^2$. Thus, $2b_1=a_0$, $4b_2=a_1$, $16b_3=a_2$, and in general $a_n=2^{2^n}b_{n+1}$, so that $x_n=2b_{n+1}$. The OEIS entry has a little information, including a link to a Usenet conversation in which Dave Rusin derives an estimate for $b_n$.

share|improve this answer
add comment

Your equation is very like the logistic map, beloved of students of discrete dynamical systems, given by $$x_{n+1}=\mu x_n(1-x_n)$$ This equation is known to have a closed form for $\mu=2$ and for $\mu=4$, and not expected to have a closed form for any other $\mu\gt0$. If you can find some substitution to bring your map into the logistic form (shouldn't be hard) then you should be able to apply what's known about the logistic map.

[EDIT: Let $x_n=2y_n$. Then $2y_{n+1}=(1/2)2y_n(2-2y_n)$ so $$y_{n+1}=y_n(1-y_n)$$ precisely the logistic map for the parameter value $\mu=1$, and the same recursion Brian gets to for $b_n$ in his answer.]

As for convergence, taking $$f(x)=(1/2)x(2-x)=x-(1/2)x^2$$ you have a fixed point at $x=0$, and $f'(0)=1$, so it's what's called a $\it non-hyperbolic$ fixed point. That's the hard case in the theory of discrete dynamical systems. The convergence will be slower than exponential, but I'm not seeing immediately how much slower.

share|improve this answer
add comment

Your Answer


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.