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?



Convergence rate of a sequence
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}<a\_k-10a\_k^3$. 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.


