Use a divide and conquer algorithm to find f(n)

Question

Use $f(1) = a$ and $f(n) = 3f(n/2) + bn$ to show that $f(n)= a(3^m) + 2(b)(3^m) - b(2^{m+1})$. Also note that $n=2^m$

Using the recurrence relation: $f(n)= a^m (f(1)) + \sum_{i=1}^{m} (a^{m-i}(g(b^i))$ we have:

$$f(n)= 3^m(a) + \sum_{i=1}^{m} (3^{m-i}(b(2^m))$$

However I am unsure how to simplify the sum.

Answer 1

Concerning your sum, notice first that the factor $b2^m$ does not depend on the index $i$, and so you can move it outside of the sum as in:

$$\sum_{i=1}^m 3^{m-i}b2^m = b2^m\sum_{i=1}^m3^{m-i}.$$

So you need only concentrate on the sum $\sum_{i=1}^m3^{m-i}$. You know that $3^{m-i} = 3^m/3^i = 3^m\cdot\left(\frac{1}{3}\right)^i$, so you can rewrite the sum as:

$$\sum_{i=1}^m3^{m-i} = 3^m\sum_{i=1}^m\left(\frac{1}{3}\right)^i.$$

You are then left with figuring out the value of $\sum_{i=1}^m\left(\frac{1}{3}\right)^i$, but this is a so-called finite geometric series, whose value you can find my plugging into the formula given (note that the formula on the wiki page starts at $i=0$).