1
$\begingroup$

Let $a_1 = 0$ and $a_i \le \alpha + \beta a_{i-1}$. I am looking for an upper bound on $a_i$ that depends only on $\alpha$ and $\beta$ and $i$.

If it helps, $\alpha, \beta \ge 0$.

$\endgroup$
  • $\begingroup$ The key factor is that, $a_i / \beta^i \le a_{i-1} / \beta^{i-1} + \alpha / \beta^i$, and sum up. $\endgroup$ – Yai0Phah May 27 '12 at 9:18
  • $\begingroup$ For $\beta \ge 0$. Another way is that, first try to solve the equation $x = \alpha + \beta x$, get the solution $x = x_0$, then $a_i - x_0 \le \beta(a_{i-1} - x_0)$. $\endgroup$ – Yai0Phah May 27 '12 at 9:19
2
$\begingroup$

If $\beta \geq 0$ then

$$ a_i \leq \frac{\beta^{i-1} - 1}{\beta - 1}\alpha. $$

This follows by induction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think that's right, thanks! It is nice that the upper bound is exactly the sum of a geometric series with $b_1 = \alpha$ and $b_i = \beta b_{i-1}$. $\endgroup$ – kloop May 27 '12 at 9:26
2
$\begingroup$

The worst case is clearly $a_n=\alpha+\beta a_{n-1}$. Let $b_n=a_n-d$ for some as yet unknown constant $d$. Then $a_n=b_n+d$, so the recurrence is $b_n+d=\alpha+\beta(b_{n-1}+d)=\alpha+\beta b_{n-1}+\beta d$, and therefore $b_n=\beta b_{n-1}+\big(\alpha+(\beta-1) d\big)$. Assuming that $\beta\ne 1$, we can set $d=-\alpha/(\beta-1)$, so that $b_n=\beta b_{n-1}$. Clearly, then, $b_n=\beta^{n-1}b_1$, where $b_1=a_1-d=\alpha/(\beta-1)$, and if follows that

$$a_n=b_n+d=\frac{\alpha\beta^{n-1}}{\beta-1}-\frac{\alpha}{\beta-1}=\frac{\alpha}{\beta-1}(\beta^{n-1}-1)\;.$$

Thus, for $\beta>0$ your upper bound is $$\frac{\alpha}{\beta-1}(\beta^{n-1}-1)\;.$$

For $\beta=1$, of course, $a_n=\alpha(n-1)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Would the downvoter care to explain what’s wrong with the argument? $\endgroup$ – Brian M. Scott May 27 '12 at 9:18
  • $\begingroup$ I didn't downvote, but I am somewhat worried about the case $\beta < 1$ - doesn't it mean you will get a negative lower bound, which of course doesn't have to be true? $\endgroup$ – kloop May 27 '12 at 9:24
  • 3
    $\begingroup$ @kloop: You’re quite right: I made a careless algebra error. Thanks: your comment was constructive and enabled me to catch and fix it. $\endgroup$ – Brian M. Scott May 27 '12 at 9:38

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.