0
$\begingroup$

I came across a sequence and tried to find out to what it converges. I have a conjecture and a proof for it, but I am not sure whether it is correct. The sequence develops in the following matter: \begin{align*} x_1 &= \frac{1}{2} - s \\ x_2 &= \frac{1}{2} - s + \frac{1}{2}x_1^2 \\\vdots \\x_t &= \frac{1}{2} - s + \frac{1}{2}x_{t-1}^2 \end{align*} where $s \in (0,\frac{1}{2})$.

So my conjecture is that this sequence converges to $1 - \sqrt{2s}$ whenever $t$ tends to infinity, numerically it seems to be right.

So far I have been thinking about the following approach: Suppose that the sequence converges to some $\bar{x}$, then the average of that sequence must also converge to $\bar{x}$. Therefore, it must hold that $\frac{1}{t} \sum\limits_{i=1}^{t}x_i$ tends to $\bar{x}$ whenever $t$ tends to infinity. Now, summing up the equations describing the sequence we have: \begin{align*} \sum\limits_{i=1}^{t} x_i = t\cdot(\frac{1}{2} - s) + \frac{1}{2}\sum\limits_{i=1}^{t-1} x_i^2 \end{align*} Multiplying with $\frac{2}{t}$ and rearranging terms yields: \begin{align*} 2s = 1 - \frac{2}{t}\sum\limits_{i=1}^{t}x_i + \frac{1}{t}\sum\limits_{i=1}^{t-1}x_i^2 \end{align*} which we can rewrite to finally get: \begin{align*} 2s = \frac{\sum\limits_{i=1}^{t} (1-x_i)^2}{t} - \frac{x^2_t}{t} \end{align*} From this point on, I am not sure what to do. Assuming that the sequence converges to some $\bar{x}$, I know that the last term on the RHS would tend to 0. If now the first term on the RHS would tend to $(1-\bar{x})^2$, then I would indeed find that $\bar{x} = 1 - \sqrt{2s}$. So my question is whether this proof is correct or whether I am missing something.

Thanks for your help!

$\endgroup$
2
$\begingroup$

Your answer seem to be correct but let me give you another approach to this problem, hopefully an easier way.

Note that your sequence is defined by the following recurrence relation: $$x_1=\frac{1}{2}-s,\,\, x_{t+1}=\frac{1}{2}-s+\frac{1}{2}x^{2}_t=x_{1}+\frac{1}{2}x^{2}_t$$

Since $s\in(0,\frac{1}{2})$ the first term is positive. I'll drop some details but you can show using induction that the sequence is monotonically increasing and bounded by 1, so we know it converges, further more we know it converges to its supremum!

So let $L=\underset{t\to\infty}{\lim}x_t$, $x_{t+1}$ is a subsequence of $x_t$ so it converges to $L$ as well and we get the equation from the recurrence formula as t goes to infinity: $$L=(\frac{1}{2}-s)+\frac{1}{2}L^2$$

Rearranging the equation and using the quadratic formula we get: $$L=1\pm\sqrt{2s}$$

but since we know the sequence converges to its supremum and is bounded by $1$ we conclude: $L=1-\sqrt{2s}$

$\endgroup$
  • $\begingroup$ Look at this answer @P3rs3rk3r. In general if you have a difference equation and you're interested in finding a stable point of the sequence, just set the variables equal to each other and solve. Of course, this works only when the sequence converges, so we have to show this separately, as is done in this answer. $\endgroup$ – Allawonder Sep 22 '19 at 12:51
  • $\begingroup$ Thank you very much guys! $\endgroup$ – P3rs3rk3r Sep 22 '19 at 13:00
1
$\begingroup$

The proof seems fine. There are two things missing, but they are fixable.

First off, you already mentioned that you believe $\frac1t\sum_{i=1}^t(1-x_i)^2$ tends to $(1-\overline{x})^2$ if $x_i\to\overline{x}$. This is true in a more general sense. For any continuous $f:\mathbb{R}\to\mathbb{R}$ we have $\frac1t\sum_{i=1}^tf(x_i)\to f(\overline{x})$ if $x_i\to\overline{x}$. This is because $x_i\to\overline{x}$ implies $f(x_i)\to f(\overline{x})$.

Secondly, you start your proof by assuming the sequence converges, but this requires justification. This is not that difficult in this case. You can first show by induction that the sequence will always be in the interval $[0,1-\sqrt{2s}]$. You can then use that to also show that the sequence is increasing. Then because the sequence is increasing but bounded from above, it follows that it converges.

There is also an easier way to show what the limit is when you know that the limit exists. We have $$\overline{x}:=\lim_{i\to\infty}x_i=\lim_{i\to\infty}\frac12-s+\frac12x_{i-1}^2=\lim_{i\to\infty}\frac12-s+\frac12x_i^2=\frac12-s+\frac12\overline{x}^2.$$ Then using your favorite method to solve quadratics you can find $\overline{x}=1-\sqrt{2s}$.

$\endgroup$
  • $\begingroup$ Thank you very much! $\endgroup$ – P3rs3rk3r Sep 22 '19 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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