# Limit of a Sequence in $\mathbb R$

Let $0 < x_1 < 1$ and $x_{n + 1} = x_n - x_n^{n + 1}$ for $n \geqslant 1$.

Prove that the limit exists and find the limit in terms of $x_1$.

I have proved the existence but cannot manage the other part.

Thanks for any help.

-
@Thomas Decreasing sequence of positive numbers? –  Michael Greinecker Aug 24 '12 at 13:06
Looks hard. This is a "non-autonomous" recurrence, $x_{n+1}=f(n,x_n)$. I was trying to find a second recurrence $y_{n+1}=g(n,y_n)$ to use as a comparison, but I get nothing. –  Siminore Aug 24 '12 at 13:50
The convergence follows from the monotonicity. The positivity of the limit is provable. To get an exact value of the limit as an explicit function of $x_1$ is more difficult and, to venture a guess, probably not doable. Are you sure this is the question? –  Did Aug 24 '12 at 14:08
Shouldn't it be $n \ge 1$ instead of $n > 1$? –  hjpotter92 Aug 24 '12 at 14:18
Yes,I have done that . I do not know if it is at all doable or not –  Ester Aug 24 '12 at 14:19

You can clearly write each term $x_{n}$ as a polynomial in $x=x_1$, and it should be apparent that all such polynomials are $x + O(x^2)$. Then the difference $x_{n+1}-x_{n}=x_{n}^{n+1}$ is $O(x^{n+1})$, and so the coefficient of $x^{k}$ is the same for all $x_{n}$ with $n\ge k$. This allows us to determine the power series expansion of $x_\infty=\lim_{n\rightarrow\infty}x_{n}$: it is $$x_\infty(x) = x-x^2-x^3+2x^4+3x^6-20x^7+30x^8-11x^9-31x^{10}+228x^{11}+\dots$$ The OEIS doesn't have anything matching this particular sequence.

-
Doing the same thing starting with $x_2=x-x^2=:u$ you get $$\hat x_\infty(u)=u-u^3-u^4-u^5+3u^6+4u^7+4u^8+2u^9-31u^{10}-52 u^{11} +\ldots$$ which seems to converge for $|u|\leq{1\over4}$. Now truncate and put $u:=x-x^2$; then you can plot $x_\infty(x)$ over all of $[0,1]$. –  Christian Blatter Aug 25 '12 at 8:59
And doing this with $x_3 = x(1-x)(1-x^2(1-x)^2) :=u$ gets $$u-u^4-u^5-u^6-u^7+4 u^8+5 u^9+12 u^{10}+4 u^{11}+\cdots$$ –  Sasha Aug 25 '12 at 12:30
Is the radius of convergence of this series positive? –  Did Aug 28 '12 at 6:11

There is going to be some overlap with @did's post, but what follows is too big to fit into the comment field.

For a fixed, arbitrary $k \geqslant 2$, consider a sequence $y_{n+1} = y_n - y_{n}^{n+k}$ with $y_1 = x_k$. Sequence $\{y_n\}$ is the subsequence of $\{x_n\}$, hence the $x_\ast = \lim_{n \to \infty} x_n$ and $y_\ast =\lim_{n \to \infty} y_n$ are equal. The limiting value $x_\ast$ is a function of $x_1$, and $y_\ast$ is a function of $x_k$, thus: $$x_\ast(x_1) = y_\ast(x_k)$$ Few initial terms of the sequence $\{x_n\}$ read: $$x_2 = x_1 (1-x_1), \quad x_3 = x_1 (1-x_1) \left(1- \left(x_1 (1-x_1)\right)^2 \right)$$

Consider an auxiliary sequence $\{t_{n}\}$ defined as $t_{n+1} = t_n \left( 1- t_1^{n+k} \right)$, $t_1 = y_1$. Because the sequence $y_n$ is decreasing, we have: $$y_{n+1} = y_n \left( 1- y_n^{n+k-1} \right) \geqslant y_n \left( 1 - y_1^{n+k-1}\right)$$ thus $t_{n} \leqslant y_n$. The sequence $t_n$ is easily solved: $$t_n = t_1 \prod_{m=1}^{n-1} \left(1-t_1^{m+k-1} \right) = t_1 (t_1^k, t_1)_{n-1}$$ where $(a,q)_n$ denotes the q-Pochhammer symbol.

Therefore, for every $k \geqslant 2$, $$t_\infty = t_1 \cdot \left(t_1^k, t_1\right)_\infty = x_k \cdot \left(x_k^k, x_k \right)_\infty \leqslant y_\ast = x_\ast$$ The higher the $k$ chosen, the closed $t_\ast$ gets to $x_\ast$.

Here is a numerical verification in Mathematica. Define code for $x_\ast$:

xiter[{xn_, n_}] := {xn - xn^(n + 1), n + 1};
xstar[x1_Real] :=
First[NestWhile[xiter, {x1, 1}, First[#1] > First[#2] &, 2]]


Now for $y_\ast$:

yiter[k_][{yn_, n_}] := {yn - yn^(n + k), n + 1};
ystar[k_?NumberQ][y1_Real] :=
First[NestWhile[yiter[k], {y1, 1}, First[#1] > First[#2] &, 2]]


and for $t_\ast$:

tstar[k_?NumberQ][t1_Real] := t1 QPochhammer[t1^k, t1]


For comparison, this is the @did's lower bound:

didstar[x1_Real] :=
Block[{x2 = x1 (1 - x1)}, x2 (1 - x2 - x2^2)/(1 - x2)]


and code for $x_n$ as a function of $x_1$:

xn[k_Integer][x1_] :=
First[RecurrenceTable[x[n + 1] == x[n] - x[n]^(n + 1) && x[1] == x1,
x, {n, k, k}]]


Here are plots of differences between $x_\ast$ and approximations in natural and logarithmic scales:

-
I think after taking out a factor of $y_n$ the exponent should be $n+k-1$ instead of $n+k$? –  joriki Aug 25 '12 at 6:24
@joriki Thanks, I will fix the typo. –  Sasha Aug 25 '12 at 12:23

Note that $x_2=x_1(1-x_1)$ with $0\lt x_1\lt1$ hence $0\lt x_2\lt1/4$, that $(x_n)_{n\geqslant1}$ is decreasing, in particular $(x_n)_{n\geqslant1}$ converges to some value $\ell(x_1)$ in $[0,x_1)$, and that $x_n\leqslant x_2$ for every $n\geqslant2$. Hence, for every $n\geqslant2$, $x_{n+1}\geqslant x_n-x_2^{n+1}$, which implies that $x_n\geqslant x_2-x_2^3-\cdots-x_2^n$ for every $n\geqslant2$ and that $\ell(x_1)\geqslant x_2-x_2^3/(1-x_2)=x_2(1-x_2-x_2^2)/(1-x_2)$ hence $\ell(x_1)\gt0$.

Auto-quote:

To get an exact value of the limit $\ell(x_1)$ as an explicit function of $x_1$ is more difficult and, to venture a guess, probably not doable.

-
+1 I have thought much along the same lines, but have a tighter lower bound. Comments/critiques on my post are welcome as usual. –  Sasha Aug 24 '12 at 16:22