I'm trying to prove the following inequality (or something similar, up to a constant factor in either side of the inequality): $$k\cdot\sum_{i=1}^{k}x_{i}\cdot\ln\left(x_{i}\right)\geq\sum_{i=1}^{k}x_{i}\cdot\left(x_{i}-1\right)$$ where $\forall i\in\left[k\right]$, $x_i \in\left[0,k\right]$ (the $x_i$s are not necessarily natural numbers, but we can assume that they're rational if it helps), and $\sum_{i=0}^k x_i=k$.

I've tried plotting it for $k=2,3$ and ran some numerical experiments for larger $k$, and I'm 99% sure this inequality is correct, but I'm still struggling with the proof.

Up to some normalizing, I find the left-hand side quite similar to the entropy of a probability distribution, but I didn't manage to take advantage of this fact either. I also tried looking for inequalities that only hold on simplex-like hyperplanes, but couldn't find anything useful.

Any ideas? Thanks!


1 Answer 1


The function $$ f(x) = k x \ln(x) - x(x-1) $$ has the second derivative $$ f''(x) = \frac k x - 2 $$ so that it is convex on the interval $[0, k/2]$. If all $x_i$ are in the interval $[0, k/2]$ then Jensen's inequality can be applied, so that $$ \sum_{i=1}^k f(x_i) \ge k f\left( \frac 1k \sum_{i=1}^k x_i\right) = k f(1) = 0 \, , $$ which is the desired estimate.

It remains to investigate the case where $x_i > k/2$ for one $i$, say $x_k > k/2$. Then $$ \sum_{i=1}^k f(x_i) = \sum_{i=1}^{k-1} f(x_i) + f(x_k) \ge (k-1) f\left( \frac 1{k-1} \sum_{i=1}^{k-1} x_i\right) + f(x_k) \\ = (k-1) f\left( \frac {k-x_k}{k-1} \right) + f(x_k) \, . $$ Therefore we define $$ g(x) = (k-1) f\left( \frac {k-x}{k-1} \right) + f(x) \, . $$ An elementary calculation shows that $g(1) =g'(1) = 0$, and $$ g''(x) = \frac{2k(x^2-kx+\frac{k^2-k}{2})}{(k-1)x(k-x)} \ge 0 \, . $$ It follows that $g(x) \ge 0$ on $[0, k]$, and that completes the proof.

  • $\begingroup$ This only works for $x_i \geq 1$, otherwise we have $x_i - 1<0$, and the rightmost inequality in your answer doesn't hold. $\endgroup$ Sep 2, 2021 at 9:29
  • $\begingroup$ @user123: Did you have a chance to check the updated answer? It should be correct now. $\endgroup$
    – Martin R
    Sep 5, 2021 at 10:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .