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$
2
  • $\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, 2012 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, 2012 at 9:19

2 Answers 2

2
$\begingroup$

If $\beta \geq 0$ then

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

This follows by induction.

$\endgroup$
1
  • $\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, 2012 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)$.

$\endgroup$
3
  • $\begingroup$ Would the downvoter care to explain what’s wrong with the argument? $\endgroup$ May 27, 2012 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, 2012 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$ May 27, 2012 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.