0
$\begingroup$

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

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

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.