COMP 2711 Ex 19

1

Basis, $T(0)$ is true

$$T(0)=r^{0}b+a\frac{1-r^0}{1-r}=b+0=b$$

Inductive hypothesis, assume $T(k)=r^{k}b+a\frac{1-r^k}{1-r}$

$$\begin{array}{rl}T(k+1)& =rT(k)+a\\ & =r\left(r^{k}b+a\frac{1-r^k}{1-r}\right)+a\\ & =r^{k+1}b+ra\frac{1-r^k}{1-r}+a\\ & =r^{k+1}b+a\left(r\frac{1-r^k}{1-r}+1\right)\\ & =r^{k+1}b+a\left(\frac{r-r^{k+1}+1-r}{1-r}\right)\\ & =r^{k+1}b+a\left(\frac{1-r^{k+1}}{1-r}\right)\end{array}$$

By the principle of M.I., $T(n)=r^{n}b+a\frac{1-r^n}{1-r}$ for all non-negative integers $n$