1
$\begingroup$

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

  • 0
    Almost. ${}{}\:$2012-10-11

2 Answers 2

2

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

1

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.