# 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
A user tried to comment on your answer: math.stackexchange.com/a/1117835 – Normal Human Jan 24 at 16:51

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

-
Thanks for your answer! I'm interested if it can be done with induction, though. (I'll accept the answer if nobody else does it that way) – Stefan Kanev Oct 20 '13 at 13:58

I personally thinks that there is an pitfall in Daniel Fischer's solution, but I can not comment directly because lack of reputation.

Daniel used Bernoulli inequality to prove $1-\frac{n-1}{{(n+1)}^2}\le{(1-\frac1{(n+1)^2})}^{n-1}$, but the actually form of Bernoulli inequality is $1 + rn \le {(1+r)}^n$, where r is a constant, but here $r = -\frac1{(n+1)^2}$ is a function of n.

So, when can't apply Bernoulli inequality directly, but follow the induction technique. ${(1-\frac1{(n+1)^2})}^{n} \ge {(1-\frac1{(n+1)^2})} \times {(1-\frac{n-1}{(n+1)^2})}$ $= 1- \frac{n}{(n+1)^2} + \frac{n-1}{(n+1)^4}$, but what to prove is ${(1-\frac1{(n+2)^2})}^{n} \ge 1-\frac{n}{{(n+2)}^2}$, it is trivial that ${(1-\frac1{(n+2)^2})}^{n} \ge {(1-\frac1{(n+1)^2})}^{n}$, but it is easy verify that $1- \frac{n}{(n+1)^2} + \frac{n-1}{(n+1)^4} \not \ge 1-\frac{n}{{(n+2)}^2}$, so we can't conclude that ${(1-\frac1{(n+2)^2})}^{n} \ge 1-\frac{n}{{(n+2)}^2}$.

-
For every fixed $n \geqslant 1$, we have $(1+r)^{n-1} \geqslant 1 + (n-1)r$, for all $r \geqslant -1$. Then, having the fixed $n$, we can take the special value $r = -\frac{1}{(n+1)^2}$ (or, looking at my answer, rather $r = -\frac{1}{n^2}$), since that is $\geqslant -1$. – Daniel Fischer Jan 24 at 16:58
That sounds great, I got the wrong interpretation. – millise Jan 25 at 1:43