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

  • $\begingroup$ I may be wrong here, but isn't ${3 + 2 \choose 2} = 10 > 2^3$? $\endgroup$ – guidoar Apr 21 '18 at 2:48
  • $\begingroup$ You are totally right, it was a typo! $\endgroup$ – Leo Apr 21 '18 at 2:51
  • $\begingroup$ We have a "proof-verification" tag, you might consider using it for this question. $\endgroup$ – user061703 Apr 21 '18 at 2:55
  • $\begingroup$ @TrầnThúcMinhTrí thanks for the suggestion! $\endgroup$ – Leo Apr 21 '18 at 2:56

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

| cite | improve this answer | |
  • $\begingroup$ I really like this answer! It gives an even better bound and it's quite elementary. Said this I will wait to accept it because I wanted an interpretation in terms of polynomials of several variables. $\endgroup$ – Leo Apr 22 '18 at 14:42

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.

| cite | improve this answer | |

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.