# bound on recursive series

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

• The key factor is that, $a_i / \beta^i \le a_{i-1} / \beta^{i-1} + \alpha / \beta^i$, and sum up. May 27, 2012 at 9:18
• 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)$. May 27, 2012 at 9:19

If $\beta \geq 0$ then

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

This follows by induction.

• 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}$. May 27, 2012 at 9:26

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

• Would the downvoter care to explain what’s wrong with the argument? May 27, 2012 at 9:18
• 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? May 27, 2012 at 9:24
• @kloop: You’re quite right: I made a careless algebra error. Thanks: your comment was constructive and enabled me to catch and fix it. May 27, 2012 at 9:38