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

  • 0
    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)$.2012-05-27

2 Answers 2

2

If $\beta \geq 0$ then

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

This follows by induction.

  • 0
    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}$.2012-05-27
2

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

  • 3
    @kloop: You’re quite right: I made a careless algebra error. Thanks: your comment was constructive and enabled me to catch and fix it.2012-05-27