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

3 Answers 3

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
    
A user tried to comment on your answer: math.stackexchange.com/a/1117835 –  Fundamental 2 days ago

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

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

share|improve this answer
    
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 2 days ago
    
That sounds great, I got the wrong interpretation. –  user3336225 yesterday

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.