Trouble understanding the master theorem, from Jeffrey Erickson's Notes

I'm looking at Jeffrey Erickson's Notes on the master theorem (page 10).

Part (b) of the theorem states that if $T(n) = aT(\frac{n}{b})+f(n)$, $af(\frac{n}{b}) = kf(n)$ and $k>1$ then T(n) is $\Theta(n^{\log_b(a)})$. But I get a different result.

Using recursion trees we have $$T(n) = \sum_{i=0}^{\log_b(n)} a^i f\left(\frac{n}{b^i}\right) = \sum_{k=0}^{\log_b(n)} k^i f(n)\,.$$

If $k<1$ then this is $\sim f(n)$ as desired. If $k=1$ then this is $\sim \log_b(n)f(n)$ as desired. But if $k>1$ then this is an ascending geometric series, so the last term dominates. Then we have $$\sim k^{\log_b(n)}f(n) = n^{\log_b(k)}f(n)\,,$$ which is wrong; the right answer is $\Theta(n^{\log_b(a)})$. Where does my reasoning go off the rails, and what is the correct solution?

Any help is appreciated.

EDIT: I think my answer is actually right, and is equivalent to Erickson's simpler answer. Note that $k^nf(n) = k^{n-1}af(\frac{n}{b}) ... = ka^{n-1}f(\frac{n}{b^k-1}) = a^nf(\frac{n}{b^k}).$ Hence $k^{\log_b(n)}f(n) = a^{\log_b(n)}f(1) \sim n^{\log_b(a)}$.

1 Answer

You can further simplify $n^{\log_b(k)}f(n)$.

We have $\frac{a}{k}f(\frac{n}{b}) = f(n)$. If $c = \log_b(n)$, we can apply this identity $c$ times to get $\left(\frac{a}{k}\right)^c f(1)$.

So $n^{\log_b(k)}f(n) = n^{\log_b(k)}\left(\frac{a}{k}\right)^c f(1) = k^{\log_b(n)}\left(\frac{a}{k}\right)^{\log_b(n)} f(1) = a^{\log_b(n)}f(1) = \Theta(n^{\log_b(a)})$