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

Question

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.

Answer 1

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

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