This is Lemma 4 of Section 2.2.2 from "Introduction to Optimization" By Boris Polyak.
Suppose $u_{k+1} \le (1-\frac{c} {k}) u_k + \frac{d}{k^{p+1}}$ where $d>0, p>0, c>0$. If $c>p$, then \begin{align*} u_k \le \frac{d(c-p)^{-1}} {k^{-p}} + o(k^{-p}). \end{align*}
I understand his proof. But the result is a little bit against my intuition. Let us take $c=2$, $d=1$, $p=1$ and if we just expand $u_{k}$ naively, we get \begin{align*} u_{k+1} &\le \frac{k-2}{k} u_{k} + \frac{1}{k^2} \\ &\le \frac{k-2}{k} \left( \frac{k-3}{k-1} u_{k-1} + \frac{1}{(k-1)^2} \right) + \frac{1}{k^2} \\ &= \frac{(k-2)(k-3)}{k(k-1)} u_{k-1} + \frac{k-2}{k(k-1)^2} + \frac{1} {k^2} \\ &\le \cdots \end{align*} It seems to me $\frac{(k-2)!}{k!} \in \mathcal O(k^{-2})$. The term remaining is also of order $k^{-2}$. I don't see why the result is of order $k^{-1}$.