Prove that $\binom{a_1}{2} + \binom{a_2}{2} + \cdots + \binom{a_n}{2} \ge r\binom{k+1}{2} + \left(n-r\right)\binom{k}{2}$

Question

If $a_1,a_2,\cdots,a_n$ are positive integers, and $a_1+a_2+\cdots +a_n=nk+r$, where $k$ and $r$ are integers such that $0\le r<n$, prove that $$\dbinom{a_1}{2} + \dbinom{a_2}{2} + \cdots + \dbinom{a_n}{2} \ge r\dbinom{k+1}{2} + \left(n-r\right)\dbinom{k}{2}$$

Here is what I do :

Consider the function $f(x) = \dbinom{x}{2}$. Since it is convex, then by applying the Jensen's inequality, we have : $$\frac{\dbinom{a_1}{2}+\dbinom{a_2}{2}+\cdots+\dbinom{a_n}{2}}{n}\ge\dbinom{\frac{a_1+a_2+\cdots+a_n}{n}}{2}$$ $$\Rightarrow \dbinom{a_1}{2}+\dbinom{a_2}{2}+\cdots+\dbinom{a_n}{2}\ge \frac{n}{2}\left(\frac{nk+r}{n}\right)\left(\frac{nk+r}{n}-1\right)$$ $$\Rightarrow \dbinom{a_1}{2}+\dbinom{a_2}{2}+\cdots+\dbinom{a_n}{2}\ge \frac{1}{2}\left(r(k+1)+(n-r)k\right)\left(\frac{nk+r}{n}-1\right)$$ But I am stuck till here, I don't know how to get the form $r\dbinom{k+1}{2} + \left(n-r\right)\dbinom{k}{2}$.

Any help is surely appreciated, Thanks!

Answer 1

We obtain with OP's problem setting and applying Jensen's inequality \begin{align*} \color{blue}{\sum_{j=1}^n\binom{a_j}{2}}&\geq n\binom{\frac{1}{n}\sum_{j=1}^n a_j}{2}\\ &=n\binom{\frac{1}{n}(nk+r)}{2}\\ &=\frac{n}{2}\left(\frac{nk+r}{n}\right)\left(\frac{nk+r}{n}-1\right)\tag{1}\\ &=\frac{1}{2}\left(nk+r\right)\left(k+\frac{r}{n}-1\right)\\ &\,\,\color{blue}{=\frac{1}{2}\left(nk(k-1)+2rk-\frac{r}{n}(n-r)\right)}\tag{2} \end{align*}

The expression (1) is stated by OP and can be rearranged to (2).

On the other hand the right side of OPs inequality can be written as \begin{align*} &r\binom{k+1}{2}+(n-r)\binom{k}{2}\\ &\qquad=\frac{1}{2}\left(r(k+1)k+(n-r)k(k-1)\right)\\ &\qquad\,\,\color{blue}{=\frac{1}{2}\left(nk(k-1)+2rk\right)}\tag{3} \end{align*}

Since $0\leq r<n$ we see the expression in (2) is less than (3) by $\frac{r}{2n}(n-r)$ whenever $0<r<n$. We conclude Jensen's inequality is not strong enough to prove the claim.

Note, the reference given in the comment by @MartinSleziak provides a nice solution (which also makes plausible that Jensen's inequality does not work).