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} \lt 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)$ ?