Exercise 4.6.2

$\star$ Show that if $f(n) = \Theta(n^{\log_b{a}}\lg^k{n})$, where $k \ge 0$, then the master recurrence has solution $T(n) = \Theta(n^{\log_b{a}}\lg^{k+1}n)$. For simplicity, confine your analysis to exact powers of $b$.

$$ g(n) = \sum_{j=0}^{\log_b{n}-1}a^jf(n/b^j) \\ f(n/b^j) = \Theta\Big((n/b^j)^{\log_b{a}}\lg^k(n/b^j)\Big) \\ g(n) = \Theta\Big(\sum_{j=0}^{\log_b{n}-1}a^j\big(\frac{n}{b^j}\big)^{\log_b{a}}\lg^k\big(\frac{n}{b^j}\big)\Big) = \Theta(A) \\ A = \sum_{j=0}^{\log_b{n}-1}a^j\big(\frac{n}{b^j}\big)^{\log_b{a}}\lg^k\frac{n}{b^j} = n^{\log_b{a}}\sum_{j=0}^{\log_b{n}-1}\Big(\frac{a}{b^{\log_b{a}}}\Big)^j\lg^k\frac{n}{b^j} = n^{\log_b{a}}\sum_{j=0}^{\log_b{n}-1}\lg^k\frac{n}{b^j} = n^{\log_b{a}}B\\ \lg^k\frac{n}{d} = (\lg{n} - \lg{d})^k = \lg^k{n} + o(\lg^k{n}) \\ B = \sum_{j=0}^{\log_b{n}-1}\lg^k\frac{n}{b^j} = \sum_{j=0}^{\log_b{n}-1}\Big(\lg^k{n} - o(\lg^k{n})\Big) = \log_b{n}\lg^k{n} + \log_b{n} \cdot o(\lg^k{n}) = \Theta(\log_b{n}\lg^k{n}) = \Theta(\lg^{k+1}{n}) \\ g(n) = \Theta(A) = \Theta(n^{\log_b{a}}B) = \Theta(n^{\log_b{a}}\lg^{k+1}{n}) $$