# Prove an upper bound for the binomials

This is (supposed to be) an upper bound on the binomial coefficient:

$$\binom{n}{k} \le \frac{n^n}{k^k(n-k)^{n-k}}$$

If we prove it by induction for all integers $0 \le k \le n/2$, we can easily show that it generalizes for $k \le n$, because $\binom{n}{k} = \binom{n}{n-k}$.

How can we prove it by induction? I get to:

$$\binom{n}{k} \le \frac{n-k+1}{k}\frac{n^n}{(k-1)^{k-1}(n-k+1)^{n-k+1}}$$

And this is where I get stuck.

-

If we assume the monotonicity of $\left(1+\frac1n\right)^n$ as known, we can fairly straightforwardly prove it by induction if we rearrange the inequality a little to get

$$\frac{k^k}{k!} \cdot \frac{(n-k)^{n-k}}{(n-k)!} \leqslant \frac{n^n}{n!},$$

or, renaming,

$$\frac{k^k}{k!}\cdot \frac{m^m}{m!} \leqslant \frac{(k+m)^{k+m}}{(k+m)!}.$$

For $m = 0$ we have the evident $\frac{k^k}{k!}\cdot 1 \leqslant \frac{k^k}{k!}$. Then, in the induction step, we have

\begin{align} \frac{k^k}{k!}\cdot\frac{(m+1)^{m+1}}{(m+1)!} &= \frac{k^k}{k!}\cdot \frac{(m+1)^m}{m!}\\ &= \frac{k^k}{k!}\cdot \frac{m^m}{m!}\left(1+\frac1m\right)^m\\ &\leqslant \frac{(k+m)^{k+m}}{(k+m)!}\left(1+\frac1m\right)^m\qquad\qquad (\text{induction hypothesis})\\ &\leqslant \frac{(k+m)^{k+m}}{(k+m)!}\left(1+\frac{1}{k+m}\right)^{k+m}\qquad (\text{monotonicity})\\ &= \frac{(k+m+1)^{k+m}}{(k+m)!}\\ &= \frac{(k+m+1)^{k+m+1}}{(k+m+1)!}. \end{align}

We can show the monotonicity of $\left(1+\frac1n\right)^n$ by using Bernoulli's inequality. Suppose $n > 1$. Then

\begin{align} \frac1n &= \frac1{n+1} + \left(\frac1n - \frac{1}{n+1}\right)\\ &= \frac{1}{n+1} + \frac{1}{n(n+1)}\\ &< \frac{1}{n+1} + \frac{1}{n^2} \end{align}

and therefore

\begin{align} \frac{n}{n+1} &= 1 - \frac{1}{n+1}\\ &< 1 - \frac1n + \frac{1}{n^2}\\ &= 1 - \frac{n-1}{n^2}\\ &< \left(1 - \frac{1}{n^2} \right)^{n-1} \qquad\qquad (\text{Bernoulli})\\ &= \frac{(n^2-1)^{n-1}}{n^{2(n-1)}}\\ &= \left(\frac{n-1}{n}\right)^{n-1} \left(\frac{n+1}{n} \right)^{n-1}, \end{align}

which yields

$$\left(1 + \frac{1}{n-1}\right)^{n-1} = \left(\frac{n}{n-1}\right)^{n-1} < \left(\frac{n+1}{n}\right)^{n-1}\left(\frac{n+1}{n}\right) = \left(1 + \frac1n\right)^n.$$

-
Cool! Is there a short proof that $\Big(1 + \frac{1}{n}\Big)^n$ is monotonous? –  Stefan Kanev Oct 20 '13 at 16:27
Depends on what you call short. I've added a relatively short elementary one. –  Daniel Fischer Oct 20 '13 at 17:45
$$n^n=(k+(n-k))^n=\sum_{j=0}^n{n\choose j}k^j(n-k)^{n-j}\ge {n\choose k}k^k(n-k)^{n-k}.$$