I'm working on a project involving monomials and I need to prove the following preposition:
Given a set of all possible monomials that can be generated up to a degree $D$ for a set of variables, the number of ways to multiply monomials of degree $d$ and degree $a$ together is greater than the total number of monomials of degree $d+a$, if $ d+a \leq n \leq D$, where $n$ is the number of variables.
For instance, if I have the set of monomials generated by 5 variables, $<v,w,x,y,z>$, I can select all degree 2 monomials and put them in this great big set, call in $U$. So something like $vx \subset U$ will be true. I can generate all monomials of degree 3 and put in this set $V$. There will be $5 \choose 2$ ways and $5 \choose 3$ ways to do this respectively.
What I wish to show is if I take every element of $U$ and $V$ and do a multiply them together, there will be repeats that can be cancelled off. For instance, $xy, wz \subset U$ and $vwz, vxy \subset V$, but multiplying their respective elements together give the same degree 5 monomial.
More specifically, I'm trying to prove that for any $n, d, a \geq 0$, $$ \binom{n}{d} \binom{n}{a} \geq \binom{n}{d+a}$$
Intutively, this seems true. But how do I go about proving it? I've tried doing it via induction but result that was unexpected:
My induction over $n$ is:
Assume $ n \choose d$*$n \choose a$ $\geq$ $n \choose {d+a}$ is true.
Then we need to prove: $ n+1 \choose d$*$n+1 \choose a$ $\geq$ $n+1 \choose {d+a}$ is true.
This means $$\frac{((n+1)!)^2}{d!a!(n+1-d)!(n+1-a)!} \geq \frac{(n+1)!}{(d+a)!(n+1-d-a)!}$$
$$\frac{(n+1)^2(n!)^2}{d!a!(n+1-d)(n-d)!(n+1-a)(n-a)!} \geq \frac{(n+1)(n!)}{(d+a)!(n+1-d-a)(n-d-a)!}$$
$$\frac{(n+1)^2}{(n+1-a)(n+1-d)}\binom{n}{d}\binom{n}{a} \geq \frac{n+1}{n+1-d-a}\binom{n}{d+a}$$
Which means that if I can prove, $$\frac{(n+1)^2}{(n+1-a)(n+1-d)} \geq \frac{n+1}{n+1-d-a}$$ the proof will be complete.
Simplifying:
$$ \frac{(n+1)(n+1-d-a)}{(n+1-a)(n+1-d)} \geq 1$$ $$ \frac{n^2+2n+1-an-dn-a-d}{n^2+2n+1-an-dn-a-d+ad} \geq 1$$ $$ \frac{-ad}{n^2+2n+1-an-dn-a-d+ad} \geq 0$$
This obviously doesn't prove anything. Is there another way to prove this hypothesis?
Any abstract math proofs are welcome too.
Hint: Let $S_k$ denote the set of subsets of $\{1,\dots,n\}$ of size $k$. The function $f:S_d \times S_a \to \mathcal P(\{1,\dots,n\})$ given by $$ f(A,B) = A \cup B $$ is a map whose image contains $S_{d+a}$.