# Binomial inequality

Show that we have:

$$\binom{n}{s}\leq n^n$$

-
Very similar to mathoverflow.net/questions/83344/… ... –  Daniel Freedman Dec 14 '11 at 1:20
It should not be up to readers here and at MO to alert people to posts at other sites - you should have done that when you first posted the questions. Can you not make any use of the estimate given in one of the comments at MO? –  Gerry Myerson Dec 14 '11 at 1:49
Maybe I could help if the humongous font weren't yelling at me. –  Quinn Culver Dec 14 '11 at 1:56
@DevenWare, yes, I was operating on that assumption, and my point stands: when you post the same question, or two versions of a question, or two closely related questions, on two different sites, you are obliged to include a link to the other site at both places. –  Gerry Myerson Dec 14 '11 at 2:05
Quinn: the humongous font is my fault, due to an edit I made at MO, because some of us decrepit folk find LaTeX's defaults for nested expressions just a bit illegible –  user16299 Dec 14 '11 at 3:07

## 3 Answers

Any coefficient in line $n$ of Pascal triangle is at most the sum $2^n$ of the line. This proves your inequality for every $n\geqslant2$ since then $2^n\leqslant n^n$.

Or:

Note that $\displaystyle{n\choose s}=\frac1{s!}\prod\limits_{k=0}^{s-1}(n-k)\leqslant \frac1{s!}n^s\leqslant n^s$. This proves your inequality for every $n\geqslant s$ since then, $n^s\leqslant n^n$. If $n\lt s$, $\displaystyle{n\choose s}=0$ hence the proof is complete for every positive $n$ and $s$.

-

Here's a more explicitly combinatorial answer. If $s > n$ then the inequality holds because $\binom{n}{s}=0$. If $s \leq n$ note that $\binom{n}{s}s!$ counts the number of injective functions from a set of $s$ elements to a set of $n$ elements. Clearly, that's less than the number of all functions from a set of $n$ elements to another set of $n$ elements, and there are $n^n$ such functions. Since we have $\binom{n}{s}\leq\binom{n}{s}s!$ and $\binom{n}{s}s!\leq n^n$, the desired inequality holds.

-

$$n^n=(s+(n-s))^n = \sum_{i=0}^n \binom{n}{i}s^i(n-s)^{n-i}\ge \binom{n}{s}s^s(n-s)^{n-s}\ge \binom{n}{s}$$

-