Suppose we have a sequence of non-negative real numbers $m_1,...,m_N$, and let $k\in\mathbb{R}$ such that \begin{equation} \sum_{i=1}^{N}m_i \leq N \cdot k. \end{equation}
I am interested in an upper bound of the quantity of $\binom{N}{2}$ additions of differences: \begin{equation} \sum_{i,j}^N \lvert{m_i-m_j}\rvert, \end{equation} with respect to $k$. Note that in the sum, if the pair $(i,j)$ is selected, then $(j,i)$ will not be repeated. I did various experiments, and turned out that $\binom{N}{2}k$ certainly works in many examples, but I am not sure if it is true or is there a proof? Also, is there any tighter bounds with respect to $k$?
Answer: The best possible upper bound you can give is $N(N-1)k$.
$\hspace{1.8cm}$This is double your answer of $\binom{N}2k$.
Proof: WLOG, $m_1<m_2<\dots<m_n$. Then the sum does not require absolute values: $$ \sum_{i<j}(m_j-m_i) $$ If you were to write out all $\binom{N}2$ of those differences, and collect like terms, you would get a sum like $$ c_1m_1+c_2m_2+\dots+c_nm_n $$ Explicitly, $c_k$ is the number of times $m_k$ appears on the positive end of the difference, minus the number of times it appears on the negative end. With some thought, you can show $$ c_k=(k-1)-(N-k)=2k-N-1 $$ The maximum value of $c_k$ is $c_N=N-1$. Therefore, $$ \sum_{k=1}^N c_km_k\le (N-1)\sum m_k\le(N-1)Nk $$ This bound is attainable when $m_n=Nk$, and the rest of the $m_i$ ($1\le i\le N-1$) are zero.