Show that if \(f(n) = \Theta(n^{\log_b a} \lg^k n)\), where \(k \geq 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\).

We have a recurrence of form \(T(n) = aT(n/b) + f(n)\) which, based on equation 4.21 has the following solution

\[T(n) = \Theta(n^{\log_b a}) + \sum\limits_{j=0}^{\log_{b} n-1} a^j f(n/b^j)\]

Since we have been provided with asymptotic information about \(f(n)\) let’s use that to better define this solution

\[\begin{split} T(n) & = \Theta(n^{\log_b a}) + \sum\limits_{j=0}^{\log_{b} n-1} a^j \Theta\left((n/b^j)^{\log_b a} \lg^k (n/b^j)\right) \\ & = \Theta(n^{\log_b a}) + \Theta \left( \sum\limits_{j=0}^{\log_{b} n-1} a^j (n/b^j)^{\log_b a} \lg^k (n/b^j)\right) \\ & = \Theta(n^{\log_b a}) + \Theta \left( n^{\log_b a} \sum\limits_{j=0}^{\log_{b} n-1} \left( \frac{a}{b^{\log_b a}} \right)^j \lg^k (n/b^j)\right) \\ & = \Theta(n^{\log_b a}) + \Theta \left( n^{\log_b a} \sum\limits_{j=0}^{\log_{b} n-1} \lg^k (n/b^j)\right) \\ \end{split}\]

Let’s pause here for a moment to consider the term trapped by the summation:

\[\begin{split} \lg^k(n/b^j) & = ( \lg n - \lg b^j)^k \\ & = \lg^k n - \lg^k b^j \\ \end{split}\]

The right term is troublesome to define, but considering the upper limit of the summation is \(\log_{b} n -1\) we can deduce that \(\lg^{k}b^j\) at this upper limit will be \(\lg^k b^{\log_b n - 1} = \lg^k (n-1) < \lg^k{n}\) which means we can safely remove this term from the summation without impacting the ultimate running time. With this in mind, let’s pick up where we left off:

\[\begin{split} T(n) & = \Theta(n^{\log_b a}) + \Theta \left( n^{\log_b a} \sum\limits_{j=0}^{\log_{b} n-1} \lg^k (n/b^j)\right) \\ & = \Theta(n^{\log_b a}) + \Theta \left( n^{\log_b a} \sum\limits_{j=0}^{\log_{b} n-1} \lg^k n\right) \\ & = \Theta(n^{\log_b a}) + \Theta ( n^{\log_b a} \log_b n \lg^k n) \\ & = \Theta(n^{\log_b a}) + \Theta ( n^{\log_b a} \lg^{k+1} n) \\ & = \Theta ( n^{\log_b a} \lg^{k+1} n) \\ \end{split}\]