What is the order of $\sum_{i=1}^{n-1}(n-i)(k-i)\log(k-i)$?

Question

Let $n<k$ and

$$f(n,k)=\sum_{i=1}^{n-1}(n-i)(k-i)\log(k-i)$$

What is $O(f(n,k))$?

I cannot solve this. Can you help?

With simply inequalities, I found that $f(n,k) = O(n^2k\log(k))$.

Answer 1

Looking at the sum, my inclination is to get $i$ by itself inside the $\log$ and distribute.

We must have $i < k$. Since we can have $i = n-1$, $n-1 < k$ so $n \le k$.

Let $k = n+m$ where $m \ge 0$.

$\begin{array}\\ f(n,k) &=\sum_{i=1}^{n-1}(n-i)(k-i)\log(k-i)\\ &=\sum_{i=1}^{n-1}(n-i)(n+m-i)\log(n+m-i)\\ &=\sum_{i=1}^{n-1}(i)(i+m)\log(i+m)\\ &=\sum_{i=m+1}^{m+n-1}(i-m)i\log(i)\\ &=\sum_{i=m+1}^{m+n-1}i^2\log(i)-m\sum_{i=m+1}^{m+n-1}i\log(i)\\ &=S_2(m+n-1)-S_2(m)-m(S_1(m+n-1)-S_1(m))\\ &=S_2(k-1)-S_2(k-n)-(k-n)(S_1(k-1)-S_1(k-n))\\ &< S_2(k)\\ \end{array} $

where $S_j(n) =\sum_{i=1}^{n}i^j\log(i) $.

Approximating the sums by integrals (and using Wolfy), $S_k(n) \approx \frac{m^{k + 1} ((k + 1) \ln(m) - 1)}{(k + 1)^2} \approx \frac{m^{k + 1} \ln(m)}{k + 1} $ so $S_1(m) \approx \frac12 m^2\ln(m) $ and $S_2(m) \approx \frac13 m^3\ln(m) $.

Therefore $f(n, k) = O(k^3\ln(k)) $.

If you know more about the values of $n$ and $k$, you can get a more accurate estimate.