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

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.

• Do you know anything about $M_1$ and $M_2$, or are those the same as $N_1$ and $N_2$? – Robert Israel Dec 1 '20 at 15:18
• There is only $M$, not $M_1, M_2$. – user249018 Dec 1 '20 at 15:27
• I corrected the mistake. Thanks – 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$$.

• +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}$ – Henry Dec 22 '20 at 13:09
• @Henry Yes, thank you! – cosmo5 Dec 22 '20 at 13:10