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?

  • 1
    $\begingroup$ You can get a real binomial coefficient with \binom{a_i}{r}, for instance. $\endgroup$ – Brian M. Scott Jun 23 '16 at 21:48
  • $\begingroup$ thanks for your editing :) $\endgroup$ – 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$.

  • $\begingroup$ 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? $\endgroup$ – Mahmoud Jun 23 '16 at 23:13
  • $\begingroup$ @Mahmoud: Yes, $a$ is the average, but in order for it to be an integer, the sum must be a multiple of $n$. $\endgroup$ – Brian M. Scott Jun 23 '16 at 23:14
  • $\begingroup$ yes you are right... I just noticed that now. thanks again :) $\endgroup$ – Mahmoud Jun 23 '16 at 23:15
  • $\begingroup$ @Mahmoud: You’re welcome. $\endgroup$ – Brian M. Scott Jun 23 '16 at 23:16
  • $\begingroup$ @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. $\endgroup$ – Mark Fischler Jun 27 '16 at 16:25

I figured out another solution using Jensen's inequality.


$$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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.