# upper bound involving recursions

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$ ?

• Your inequality $a_k \le a_0 - k/2$ is not true at all. For example, you could have all $a_k = 0$. Jul 31, 2017 at 21:55
• Sorry about the confusion. Its true for all $a_k >1$. Will update the question. Jul 31, 2017 at 22:05

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}$.