I need to prove the inequality ${M}\choose{N_1}$ ${M}\choose{N_2}$ $\leq$ ${2M}\choose{N_1+N_2}$ for $M, N_1, N_2 \in \mathbb{N},\,M\geq N_1,N_2$.

I wanted to prove it by induction. But since we are given 3 variables running, I was confused if the natural induction, as I know it, can be used in this case. Can you tell me if proving by induction is possible and necessary in this example ?

We get $N_1, N_2, N_1+N_2$ fractions from ${M}\choose{N_1}$,${M}\choose{N_2}$, and ${2M}\choose{M_1+M_2}$, respectively. Without loss of generality, we assume $N_1\geq N_2.\,$An appropriate approximation of all fractions from left to right leads to: $$ \frac{M}{N_1}\frac{M-1}{N_1 -1}\frac{M-2}{N_1-2}\cdots \frac{M-(N_1-1)}{1} \cdot\frac{M}{N_2}\frac{M-1}{N_2 -1}\frac{M-2}{N_2-2}\cdots \frac{M-(N_2-1)}{1}\leq \frac{2M}{N_1+N_2}\cdots $$ For the second fraction from the left I get: $\frac{M-1}{N_1 -1}=\frac{2M-2}{2N_1-2}\geq\frac{2M-1}{2N_1-1}\leq\frac{2M-1}{N_1+N_2-1}.$ The last term in the last inequality is not the convenient approximation for $\frac{M-1}{N_1 -1}$ unless we got $\leq$ instead of $\geq$ sign in the last inequality.

Can somebody provide some hint how to go further ? Thanks.

  • 3
    $\begingroup$ Do you know anything about $M_1$ and $M_2$, or are those the same as $N_1$ and $N_2$? $\endgroup$ – Robert Israel Dec 1 '20 at 15:18
  • $\begingroup$ There is only $M$, not $M_1, M_2$. $\endgroup$ – user249018 Dec 1 '20 at 15:27
  • $\begingroup$ I corrected the mistake. Thanks $\endgroup$ – user249018 Dec 1 '20 at 15:35

We prove by induction on $M$. Base case is easy. If it's true for $M=k$, we now prove it's true for $M=k+1$.

First note that if $N_1=0, N_1=k+1, N_2=0$ or $N_2=k+1$ it's trivial.

If not, then $1 \le N_1, N_2 \le k$.

$$ \binom{k+1}{N_1} \binom{k+1}{N_2}=\left(\binom{k}{N_1}+\binom{k}{N_1-1}\right) \left(\binom{k}{N_2}+\binom{k}{N_2-1}\right) $$

Can you start from here?

$$=\binom{k}{N_1}\binom{k}{N_2}+\binom{k}{N_1}\binom{k}{N_2-1}+\binom{k}{N_2}\binom{k}{N_1-1}+\binom{k}{N_1-1}\binom{k}{N_2-1}\\ \le \binom{2k}{N_1+N_2}+\binom{2k}{N_1+N_2-1}+\binom{2k}{N_1+N_2-1}+\binom{2k}{N_1+N_2-2}\\ =\binom{2k+1}{N_1+N_2} + \binom{2k+1}{N_1+N_2-1} = \binom{2k+2}{N_1+N_2}$$


There is simple combinatorial argument.

Consider two disjoint partitions of set $A=\{ 1,2,3,\ldots, 2M\}$ : $B=\{ 1,2,3,\ldots, M\}$ and $C=\{ M+1,M+2,M+3,\ldots, 2M\}$

LHS denotes choosing $N_1$ members from $B$ and $N_2$ members from $C$.

RHS denotes choosing $N_1 + N_2$ members from $A$ where there are more possibilities. The $N_1$ choices can be made from both halves (same for $N_2$), for which there are clearly more number of ways. In fact, RHS includes LHS case. The inequality follows.

Also equality occurs for $N_1=N_2=M$, when number of choices (each binomial coefficient) is $1$.

  • $\begingroup$ +1 This naturally extends to $\displaystyle {M_1 \choose N_1}{M_2 \choose N_2}\le {M_1 +M_2 \choose N_1+N_2}$ $\endgroup$ – Henry Dec 22 '20 at 13:09
  • $\begingroup$ @Henry Yes, thank you! $\endgroup$ – cosmo5 Dec 22 '20 at 13:10

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.