Turán's graph $T_{k, n}$ has more edges than any other $k$-partite graph with $n$ vertices. In Bondy and Murty's Graph Theory, exercise $1.1.11$ defines something called Turán's graph $T_{k, n}$, as a complete, $k$-partite graph where all parts are of size $\lceil \frac{n}{k} \rceil$, or $\lfloor \frac{n}{k} \rfloor$. I want to show the following: 

$T_{k, n}$ has more edges than any other complete $k$-partite graph with $n$ vertices.

I know from part $a)$ that in this case, the number of edges of a complete, $k$-partite graph is $\frac{1}{2} \sum_{i=1}^{k} a_{i}(n-a_{i})$, where $a_{i}$ are the sizes of the parts $A_{i}$. So I want to prove that if $n=kq+r$, $0 \leq r < n$, $q = \lfloor \frac{n}{k} \rfloor$, $a_{1}= \space ... \space =a_{r}=q+1$, $a_{r+1}= \space ... \space =a_{k} = q$, and $b_{i}$ any other sequence of $k$ positive numbers such that $\sum_{i=1}^{k} b_{i} = n$, that $$\sum_{i=1}^{k} a_{i}(n-a_{i}) \geq \sum_{i=1}^{k} b_{i}(n-b_{i}).$$ Is there an elementary-inequality way of proving this? I've tried Lagrange multipliers, but it seems like overkill, and it'd require further discussion since $a_{i}$ can only be positive integers, not real numbers.
 A: The only real way avoid "further discussion" to deal with the issue of integers is what they call a smoothing argument.
First, if we have $b_i - b_j\ge 2$ for any $i,j$, then replacing them by $b_i' = b_i - 1$ and $b_j' = b_j + 1$ while leaving all terms the same will increase the sum:
$$\sum_{i=1}^k b_i (n-b_i) < \sum_{i=1}^k b_i' (n-b_i').$$
This is easy to check, since only two terms of the sum change, and the total change is by $2(b_i - b_j - 1) > 0$.
Second, if some of the parts do not have size $\lfloor \frac nk \rfloor$ or $\lceil \frac nk \rceil$, then the largest part and the smallest part must differ in size by at least $2$:


*

*The average size is $\frac nk$, so the largest part must have size at least $\lceil \frac nk \rceil$ and the smallest part must have size at most $\lfloor \frac nk \rfloor$. 

*If $\frac nk$ is not an integer, then this already guarantees a difference of $2$ unless the largest part has size exactly $\lceil \frac nk \rceil$ and the smallest part has size exactly $\lfloor \frac nk \rfloor$.

*If $\frac nk$ is an integer, then any part of size less than $\frac nk$ forces a part of size greater than $\frac nk$, and vice versa.


In such a case, the inequality above shows that such a $k$-partite graph cannot have the maximum number of edges. This leaves the Turán graph as the only possibility.
