Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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}.$$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.