Proof of a lower bound of the recurrence relation (the CLRS's 4.6-2 exercise)
All we need to prove is the following, where $b&gt;1, k\ge 0$ and $k$ may or may not be an integer.
$$\sum_{j=0}^{\lfloor\log_b n\rfloor} \left(\log_b\left(\frac n{b^{j}}\right)\right)^k=\Omega((\log_b n)^{k+1})$$

In order to show the idea of the proof clearly, assume that $n = b^m$. The above estimate is
$$\sum_{j=0}^{m} (m-j)^k=\Omega(m^{k+1})$$

Here is the proof.

$$\sum_{j=0}^{m} (m-j)^k=\sum_{i=1}^m i^k\ge\sum_{i=1}^m \int_{i-1}^{i} u^k du=\int_{0}^{m} u^k du = \left.\frac{u^{k+1}}{k+1}\right |^m_0= \frac{m^{k+1}}{k+1} $$