# Convergence rate of a sequence

Suppose $$x_0=x_1=1$$, define $$y_k=x_k+\frac{1}{2}(x_k-x_{k-1})$$ and $$x_{k+1}=y_k-\eta y_k^3$$ where $$\eta\in(0,1/8)$$. If we know $$x_k\to 0$$ as $$k\to\infty$$. How to show that $$x_k=\Theta(1/\sqrt{k})$$?

It suffices to show that $$x_k^{-2}=\Theta(k)$$. By Taylor expansion, we have $$x_{k+1}^{-2} = (y_k-\eta y_k^3)^{-2} = y_k^{-2}(1-\eta y_k^2)^{-2} = y_k^{-2}(1+2\eta y_k^2+o(y_k^2)) = y_k^{-2}+2\eta+o(1)$$ It seems that $$x_{k+1}^{-2}$$ and $$y_k^{-2}$$ form a linearly increases sequence. If here $$y_k^{-2}$$ is replaced by $$x_k^{-2}$$, then we obtain exactly $$x_k^{-2}=\Theta(k)$$. However, $$y_k^{-2}\ne x_k^{-2}$$, and I got stuck at this step. Can someone give a hint?

• Are you interested in the case where $\eta$ is close to $\frac{1}{8}$? I'm pretty sure I have a proof but it works better if $\eta<\frac{1}{12}$, if $\eta$ is close to $\frac{1}{8}$ it seems like a more complicated argument would be needed Commented Oct 12, 2022 at 22:57
• In fact I think the delicate part is proving that $x_k>0$ for all $k$ and that $\frac{x_{k+1}}{x_k}\to 0$, which seem like they should be obvious at first glance. The condition $\eta<\frac{1}{8}$ is to ensure that the sequence $x_k$ doesn't become negative? Commented Oct 12, 2022 at 23:13
• Thanks for your reply. I can prove $x_{k+1}/x_k\in(0,1)$ for sufficiently large $k$, which means that eventually $x_k$ will not change sign and $|x_k|$ will be decreasing (it is possible to be negative). If we want $x_k=\Theta(1/\sqrt{k})$, then we need to show $x_{k+1}/x_k\to 1$. However, I can only show $x_{k+1}/x_k$ converges to either $1$ or $1/2$, using the result in mathoverflow.net/questions/432262/convergence-of-a-sequence. I don't know how to exclude the possibility that $x_{k+1}/x_k\to 1/2$, and it that is true, then the convergence rate of $x_k$ would be linear convergence. Commented Oct 13, 2022 at 3:52
• For $\eta=1/8$, I run numerical experiments and it seems that the whole sequence $x_k$ is positive and decreasing. Furthermore, as $k\to\infty$, I found that $kx_k^2\to 2$. It would still be very helpful if you can write your proof for $\eta<1/12$. @SaúlRM Commented Oct 13, 2022 at 4:03
• I see. In the end I didn't need $\eta<\frac{1}{12}$, it can be improved to $\frac{1}{8}$ with one more line of argument. I wrote my answer supposing that $x_k>0$ for all $k$, although that is not obvious to me Commented Oct 13, 2022 at 14:32

Suppose that we already know that $$x_k>0\forall k$$. Clearly $$(x_k)$$ and $$(y_k)$$ are decreasing sequences which converge to $$0$$. Then we can prove that $$b_k:=\frac{x_{k}}{x_{k-1}}\to 1$$. To do it note first that $$b_k\in[0,1]\forall k$$ and

$$b_{k+1}=\frac{y_k-\eta y_k^3}{x_k}=\frac{x_k+\frac{1}{2}(x_k-x_{k-1})-\eta y_k^3}{b_kx_{k-1}}=\frac{3}{2}\frac{x_k}{b_kx_{k-1}}-\frac{1}{2b_k}-\eta\frac{y_k^3}{b_kx_{k-1}}=$$

$$=\frac{3}{2}-\frac{1}{2b_k}-\eta\frac{y_k^3}{b_kx_{k-1}}>\frac{3}{2}-\frac{1}{2b_k}-\eta\frac{x_k^3}{b_kx_{k-1}}=\frac{3}{2}-\frac{1}{2b_k}-\eta x_k^2.$$

So $$b_{k+1}>\frac{3}{2}-\frac{1}{2b_k}-\eta x_k^2$$. Now note that $$x_k<1-\frac{3}{2}\eta$$ for all $$k\geq3$$, so that $$b_{k+1}>\frac{3}{2}-\frac{1}{2b_k}-\eta(1-\frac{3}{2}\eta)^2>\frac{3}{2}-\frac{1}{2b_k}-\frac{1}{8}(1-\frac{3}{16})^2=\frac{2903}{2048}-\frac{1}{2b_k}\sim1.407-\frac{1}{2b_k}$$.

Using this you can prove by induction that $$b_k>0.7$$ for all $$k$$ (as base case you need to check $$b_2,b_3>0.7$$). Using that fact and that:

• $$b_{k+1}>\frac{3}{2}-\frac{1}{2b_k}-x_k^2$$

• $$x_k\to0$$

it's not difficult to prove that $$b_k\to 1$$.

Now let's prove that $$x_k=\Theta(\frac{1}{\sqrt{k}})$$. To do it we will compare it with the sequence $$a_k=\frac{1}{10\sqrt{k}}$$. Note that we have $$a_{k+1}. So if we prove that for big enough $$k$$ we have $$x_{k+1}>x_k-10x_k^3$$, then our series will decrease slower than $$a_k$$ and we will be done.

This is equivalent to proving $$\frac{x_k-x_{k+1}}{x_k^3}<10$$ for big enough $$k$$. So let's study $$c_k:=\frac{x_k-x_{k+1}}{x_k^3}$$. Of course $$c_k$$ is always positive, and we have

$$c_{k}=\frac{x_k-x_{k+1}}{x_k^3}=\frac{x_k-y_k+\eta y_k^3}{b_k^3x_{k-1}^3}=\frac{\frac{1}{2}(x_{k-1}-x_k)+\eta y_k^3}{b_k^3x_{k-1}^3}=\frac{1}{2b_k^3}c_{k-1}+\frac{\eta}{b_k^3}\left(\frac{y_k}{x_{k-1}}\right)^3.$$ Now using that $$b_k\to 1$$ and $$\frac{y_k}{x_{k-1}}\to1$$, the inequality implies that for big $$k$$ we have $$c_k<0.7c_{k-1}+1$$. So for big enough $$k$$ we have $$c_k<10$$, as we wanted.