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?
 A: 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.
