Combinatorial identity using polynomials of several variables [Proof verification]

Question

I have tried to prove the following result.

Prove that $\forall d,n \in \mathbb{N},d, n \geq 3$, $${{n+d}\choose{d}} \leq d^{n}$$.

The result which I'm supposed to use (and which I proved before) was that the dimension of the vectorial space $K[X_1, \dots, X_n]_d$ was ${{n+d}\choose{d}}$ where K is a field and $d \in \mathbb{N}$ is the degree of the polynomials. For that I constructed the basis of the monomials, and the resulting dimension was ${{n+d}\choose{d}}$ using stars and bars.

In other words let $\mathbb{B} = \{{x_1}^{d_1}\dots, {x_n}^{d_n} : \sum_{i=1}^{n} {d_i} = d \}$ the basis of the vectorial space $K[X_1, \dots, X_n]_d$.

What I tried to prove was that $\mathbb{B} \subset \mathbb{B'}$ where $\#(\mathbb{B'}) = d^n$.

I considered the following set $\mathbb{B'} = \{f = {x_1}^{d_1}\dots, {x_n}^{d_n} : 1\leq i \leq n , 0 < deg_{x_i} \leq d \}$. Where $deg_{x_i}$ is the degree of the polynomial in $K[X_1,\dots , X_{i-1},X_{i+1} \dots, X_n][X_i]$. Now this set clearly contains all the monomials in $\mathbb{B}$ and the cardinal of the set is $d^n$ because each monomial $x_i$ has exactly $d$ possible degrees for a total of $n$ monomials.

I know that probably this can be proved in many other (more interesting and shorter ways) but I will be glad if someone could check for any holes in my argument. Thanks for the attention.

EDIT: I have just realized that as I have defined $\mathbb{B}$, it's cardinal is actually ${{n+d-1}\choose{d}}$, which makes my attempt at proof completely invalid. But maybe I could redefine $\mathbb{B}$ and find an injection from $\mathbb{B}$ to $\mathbb{B'}$.

Answer 1

For $n,d\ge3$, we get $$ \begin{align} \frac1{d^n}\binom{n+d}{d} &=\frac1{d^n}\binom{n+d}{n}\\ &=\prod_{k=1}^3\frac{k+d}{kd}\prod_{k=4}^n\frac{k+d}{kd}\\ &\le\frac{(d+1)(d+2)(d+3)}{6d^3}\prod_{k=4}^n\frac2{\min(k,d)}\\ &\le\left(\frac16+\frac1d+\frac{11}{6d^2}+\frac1{d^3}\right)\left(\frac23\right)^{n-3}\\[6pt] &\le\frac{20}{27} \end{align} $$ Therefore, $$ \binom{n+d}{d}\le\frac{20}{27}\,d^n $$

Answer 2

I cannot prove or disprove your reasoning, but the inequality is definitely true. Proof by induction.

For $n=d=3$:

$${6 \choose 3 } \leq 3^3 $$

Suppose that:

$${{n+d}\choose{d}} \leq d^{n}$$

Let us prove that the inequality holds for $n+1$:

$${{n+1+d}\choose{d}} = \frac{(n+1+d)!}{(n+1)!d!}=\frac{n+1+d}{n+1}{n+d\choose d}\leq \frac{n+1+d}{n+1}d^n$$

Now we are going to prove that:

$$ \frac{n+1+d}{n+1} \leq d$$

This inequality is equivalent to:

$$ 1 + \frac{1}{n} \leq d$$

which is obvious.

Let us now prove that the starting inequality holds for $d+1$:

$${{n+d+1}\choose{d+1}}= \frac{(n+d+1)!}{n!(d+1)!}=\frac{n+d+1}{d+1}{n+d\choose d}\leq(1+\frac{n}{d+1}) d^n$$

We should now prove that:

$$(1+\frac{n}{d+1}) d^n \leq (d+1)^n$$

which is equivalent to:

$$ 1+\frac{n}{d+1} \leq (1+\frac{1}{d})^n$$

...and this is obvious because:

$$ (1+\frac{1}{d})^n \ge 1+\frac{n}{d} \ge 1+\frac{n}{d+1}$$

This completes two induction steps, for $n+1$ and $d+1$.

Actually, it seems that equality is never reached.