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
    Commented Jul 31, 2017 at 21:55
  • $\begingroup$ Sorry about the confusion. Its true for all $a_k >1$. Will update the question. $\endgroup$
    – Kcafe
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .