Suppose that I have the following recursion for all $a\_k >1$: $a\_{k+1}^2 \leq a\_k^2 - a\_k$. Then one can see that the following inequality is true (proved via induction): $a\_k \leq a\_0 - \frac{k}{2}$. Now if I update my recursion as $a\_{k+1}^2 \leq a\_k^2 - a\_k +\frac{1}{2}$, the inequality, $a\_k \leq a\_0 - \frac{k}{2}$, does not hold anymore. 


I was wondering if one can show a modifed inequality of the form $a\_k \leq a\_0 - \frac{k^\alpha}{b}+c$, for some value of $\alpha,b,c$ holds true. But it seems to involve conditions on $a\_0$ which seems unsatisfactory. 


Can we show an upper bound on $a\_k$ with the second recursion in terms of $a\_0$ and some function of $k$ ? 



upper bound involving recursions
Rewrite $a\_{k+1}^2 \leq a\_k^2 - a\_k + \frac12$ as $4a\_{k+1}^2 \leq (2a\_k-1)^2 + 1$. Then
$$\frac{2a\_{k+1}}{2a\_k-1} \leq \left(1+\frac{1}{(2a\_k-1)^2}\right)^{1/2} \leq 1 + \frac{1}{2(2a\_k-1)^2} \leq 1 + \frac{1}{2(2a\_k-1)}.$$
Hence, $a\_{k+1} \leq a\_k - \frac{1}{4}$, implying that $a\_k \leq a\_0 - \frac{k}{4}$.


