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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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