1

These are from my textbook examples, introduced as Theorem 1,

If $T(n)=rT(n-1)+a,$ $T(0)=b$ and $r\ne 1$,

$T(n)=r^nb+\left[\frac{a(1-r^n)}{(1-r)}\right]$

And I supposed to solve other recurrence problems applying the Theorem 1

But I don't understand how they reached to that point - I don't get the point where they had $\left[\frac{(1-r^n)}{(1-r)}\right]$ value.

Michael Grant
  • 19,450
Minjae
  • 207

1 Answers1

1

Notice that

$$\frac{1-r^n}{1-r} = \sum_{k=0}^{n-1} r^k$$

Then it's easy to see that :

$$T(1) = rT(0)+a$$

$$T(2) = r(rT(0)+a)+a = r^2T(0) + a(1 + r)$$

$$T(3) = r(r^2T(0) + a(1 + r)) + a = r^3T(0) + a(1 + r + r^2)$$

So you get by induction

$$T(n) = r^nT(0) + a(1 + r + r^2 + \cdots + r^{n-1})$$

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

Tryss
  • 14,310
  • I still don't get this part: $a(1+r+r2+⋯+rn−1)$

    becomes $a(1−r^n)/(1−r)$

    Is there any specific formula that turns previous one to the next step?

     – Minjae Jul 07 '15 at 03:48
  • @Minjae It's the sum of the terms of a geometric sequence. It's a classical formula you need to know – Tryss Jul 07 '15 at 03:54
  • Oh I see it. But still, I'm supposed to solve the recurrence, $M(n)=3M(n-1)+1$ with base case of $M(1)=1$, applying the Theorem above. I have no idea how to apply it. Can you give me a hint for that? – Minjae Jul 07 '15 at 04:06