Has anyone seen an inequality of this form before? It seems to be true (based on extensive testing), but I am not able to prove it.

Let $a_1,a_2,\ldots,a_k$ be non-negative integers such that $\sum_i a_i = A$. Then, for any non-negative integer $B \le A$: $$ \sum_{(b_1,\ldots,b_k): \sum_i b_i = B} \prod_i \frac{\binom{a_i}{b_i}}{\binom{A-a_i}{B-b_i}} \ge {\binom{A}{B}}^{2-k}. $$ The sum on the left is over all tuples $(b_1,b_2,\ldots,b_k)$ of non-negative integers, with $b_i \le a_i$ for all $i$, whose sum is equal to $B$.


1 Answer 1


By Cauchy–Bunyakovsky–Schwarz inequality we have $$ \left(\sum \prod_i \frac{\binom{a_i}{b_i}}{\binom{A-a_i}{B-b_i}}\right)\left(\sum\prod_i \binom{a_i}{b_i}\binom{A-a_i}{B-b_i}\right)\geqslant \left(\sum \prod_i\binom{a_i}{b_i}\right)^2=\binom{A}{B}^2 .$$

Thus it suffices to prove that $$ \sum\prod_i \binom{a_i}{b_i}\binom{A-a_i}{B-b_i}\leqslant \binom{A}B^k. $$ But RHS is just the sum of the same guys without the restriction $\sum b_i=B$.

  • $\begingroup$ Brilliant! Thank you. $\endgroup$
    – Navin K.
    Commented Mar 13, 2019 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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