Trying to prove Master Theorem from $T(n) = aT(n/b) + f(n)$

Question

Let's consider a recurrence of form $T(n) = aT(n/b) + f(n)$ where $n = b^k$ for simplicity. Then $T(n/b^k) = T(n/n) = T(1)$ but I don't know what we're usually supposed to set $T(1)$ equal to at the bottom of the recursion (a constant? $f(1)$? What?).

Then I am trying to solve the recurrence first by unrolling it:

$T(n) = aT(n/b) + f(n)$

$T(n) = a^2T(n/b^2) + af(n/b) + f(n)$

$T(n) = a^3T(n/b^3) + a^2f(n/b^2) + af(n/b) + f(n)$

...

$T(n) = a^kT(n/b^k) + \sum_{i=0}^{k-1} a^i f(n/b^i)$

If $T(1) = f(1)$ then:

$T(n) = \sum_{i=0}^{k} a^i f(n/b^i) = \sum_{i=0}^{\log_b(n)} a^i f(n/b^i)$

However I look up http://www.cs.cornell.edu/courses/cs3110/2011sp/Lectures/lec19-master/mm-proof.pdf and they say it's

$T(n) = O(n^{\log_b(a)}) + \sum_{i=0}^{\log_b(n)} a^i f(n/b^i)$

Where did I go wrong?

Answer 1

You did it correctly and it seems like the summation $\sum_{i=0}^{\log_b n}$ in the course notes should be $\sum_{i=0}^{\log_b n - 1}$. Your formula $T(n) = a^k T(n/b^k) + \sum_{i=0}^{\log_b a - 1} a^i f(n/b^i)$ simplifies to $T(n) = a^{\log_b n} T(1) + \sum_{i=0}^{\log_b a - 1} a^i f(n/b^i) = n^{\log_b a} T(1) + \sum_{i=0}^{\log_b a - 1} a^i f(n/b^i) = \Theta(n^{\log_b a}) +\sum_{i=0}^{\log_b a - 1} a^i f(n/b^i)$.