# binomial inequality with sums

Assume I have a series of numbers $a_1 \dots a_n$ where $0 \leq a_i \leq n-1$ and a positive integer $r$.

how to show that the sum of number of ways to choose $r$ from $a_i$ is at least as $n$ times the number of ways to choose $r$ from the average of $a_i$'s.

in other words, I need to show:

$$\sum_{1\leq i \leq n}\binom{a_i}r\geq n\binom{\frac1n\sum_{1\le i\le n}a_i}r$$

any idea of how to prove this? if you think it is not correct, which conditions do I need to add to make it correct?

• You can get a real binomial coefficient with \binom{a_i}{r}, for instance. – Brian M. Scott Jun 23 '16 at 21:48
• thanks for your editing :) – Mahmoud Jun 23 '16 at 21:58

The result is correct if $\sum_{i=1}^na_i$ is a multiple of $n$. Let $a=\frac1n\sum_{i=1}^na_i$; we want to show that

$$\sum_{i=1}^n\binom{a_i}r\ge n\binom{a}r\;.\tag{1}$$

Suppose that $a_i<a<a_k$. Then

\begin{align*} \binom{a_i}r+\binom{a_k}r&=\binom{a_i}r+\binom{a_k-1}r+\binom{a_k-1}{r-1}\\ &\ge\binom{a_i}r+\binom{a_k-1}r+\binom{a_i}{r-1}\\ &=\binom{a_i+1}r+\binom{a_k-1}r\;. \end{align*}

Repeatedly transferring a unit from an $a_k>a$ to an $a_i<a$ will eventually convert the $n$-tuple $\langle a_1,\ldots,a_n\rangle$ to the constant $n$-tuple $\langle a,\ldots,a\rangle$, and no transfer increases the sum of the binomial coefficients, so $(1)$ holds.

More generally, the same argument shows that if we hold $\sum_{i=1}^na_i$ constant, $\sum_{i=1}^n\binom{a_i}r$ is minimized when the integers $a_i$ are as nearly equal as possible. If the sum is a multiple of $n$, this is when all $n$ are equal; otherwise, if the sum is $qn+s$ for integers $q$ and $s$ such that $0\le s<n$, it occurs when $s$ of the $a_i$ are equal to $q+1$ and the rest to $q$.

• Thanks a lot... but I'm not sure you need to require that $\sum_{i=1}^n a_i$ is a multiple of $n$ ... your argument is based on that: $\sum_{i=1}^n (a_i - a) = 0$ , but this is correct because $a$ is the average. right? – Mahmoud Jun 23 '16 at 23:13
• @Mahmoud: Yes, $a$ is the average, but in order for it to be an integer, the sum must be a multiple of $n$. – Brian M. Scott Jun 23 '16 at 23:14
• yes you are right... I just noticed that now. thanks again :) – Mahmoud Jun 23 '16 at 23:15
• @Mahmoud: You’re welcome. – Brian M. Scott Jun 23 '16 at 23:16
• @Brian M. Scott The binomial coefficient is well defined for non-integer upper parameter (but not for non-integer lower parameter). So it appears that the proof given is valid without the restriction to the average being an integer. – Mark Fischler Jun 27 '16 at 16:25

I figured out another solution using Jensen's inequality.

define:

$$f(x) = \frac{x(x-1)\dots (x-r+1)}{r!} =: \binom{x}{r}$$ $$p_i = \frac{1}n$$

$f$ is convex for positive $x$. Pay attention that $r$ is a given constant.

Using Jensen's inequality gives:

$$\sum_{i=1}^n p_i f(a_i) \geq f\left( \sum_{i=1}^n p_i a_i \right)$$ $$\Longrightarrow \sum_{i=1}^n \frac{1}n \binom{a_i}{r} \geq \binom{ \sum_{i=1}^n \frac{1}{n} a_i}{r}$$

multiplying by $n$ gives the needed result.