# Proof of a lower bound of the recurrence relation (the CLRS's 4.6-2 exercise)

I am trying to find a solution to the ex. 4.6-2 of the Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (the third edition). It requires, for recurrence relations $$T(n)=aT(n/b)+f(n)$$ where $$a\geq 1, b > 1$$, $$n$$ is an exact power of $$b$$ and $$f(n)$$ is an asymptotically positive function, to prove that if $$f(n) = \Theta(n^{\log_ba}lg^{k}n)$$, where $$k\geq0$$, then $$T(n)=\Theta(n^{\log_ba}lg^{k+1}n)$$.

Since $$T(n) = n^{\log_ba} + g(n)$$ where $$g(n) = \sum_{j=0}^{\log_b n - 1} a^{j}f(n/b^{j})$$, I decided to consider the $$g(n)$$ function at the first. And I have shown $$g(n) = O(n^{\log_ba}lg^{k+1}n)$$ already (I think so).

But the doing the proof $$g(n) = \Omega(n^{\log_ba}lg^{k+1}n)$$ became a challenge for me.

Below is my research (with the simplified assumption $$k$$ is an integer). By condtition, there is such constant $$c$$ that

$$g(n) \geq$$

$$c \sum_{j=0}^{\log_b n - 1} a^{j}(n/b^{j})^{log_ba}log^{k}(n/b^{j}) =$$

$$cn^{\log_ba}\sum_{j=0}^{\log_b n - 1} log^{k}(n/b^{j}) =$$

$$cn^{\log_ba}\sum_{j=0}^{\log_b n - 1}(logn - logb^{j})^{k} =$$

$$cn^{\log_ba}\sum_{j=0}^{\log_b n - 1}\sum_{i=0}^{k} {k \choose i}log^{k-i}n(-logb^{j})^{i} =$$

$$cn^{\log_ba}log^{k}n\sum_{j=0}^{\log_b n - 1}\sum_{i=0}^{k} {k \choose i}(-logb^{j}/logn)^{i} =$$

$$cn^{\log_ba}log^{k}n \biggl(log_bn + \sum_{j=0}^{\log_b n - 1}\sum_{i=1}^{k} {k \choose i}(-logb^{j}/logn)^{i} \biggr) \geq$$

$$c'n^{\log_ba}log^{k+1}n - cn^{\log_ba}log^{k}n\sum_{j=0}^{\log_b n - 1}\sum_{i=1}^{k} {k \choose i}(logb^{j}/logn)^{i} =$$

$$A(n) - B(n) = \Theta(n^{\log_ba}lg^{k+1}n) - B(n)$$

Actually I am stuck with it. I can not show that $$B(n)$$ grows slower than $$A(n)$$. For instance, since $$(logb^{j}/logn)^{i} \le 1$$ we are able to enhance our $$\geq$$ condition by the substitution $$B(n)$$ to some fucntion $$B'(n)$$ with the sums of binominal coefficients only. But then finally $$B'(n)$$ has $$n^{\log_ba}log^{k+1}n$$.

So how to prove $$g(n) = \Omega(n^{\log_ba}lg^{k+1}n)$$ ?

All we need to prove is the following, where $$b>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})$$
$$\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}$$