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

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.

• Hi Michael and welcome to the site. It is advisable to learn math typesetting with LaTeX as it makes it easier for other people to read the posts (and to bother trying to understand and answer). It is a good thing you are showing what you have tried. If you are a new user typically you will get help with typesetting but being sloppy with it later on could give down votes and that people don't bother with the question. Hint: you can use these types of parentheses to get "a^{b+c}" to get $a^{b+c}$ – mathreadler Oct 22 '15 at 17:55

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