bound on recursive series

Question

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

Answer 1

If $\beta \geq 0$ then

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

This follows by induction.

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