0
$\begingroup$

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.

$\endgroup$

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$ Oct 20, 2013 at 13:58
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Cool! Is there a short proof that $\Big(1 + \frac{1}{n}\Big)^n$ is monotonous? $\endgroup$ Oct 20, 2013 at 16:27
  • $\begingroup$ Depends on what you call short. I've added a relatively short elementary one. $\endgroup$ Oct 20, 2013 at 17:45
  • $\begingroup$ A user tried to comment on your answer: math.stackexchange.com/a/1117835 $\endgroup$
    – user147263
    Jan 24, 2015 at 16:51
-1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ Jan 24, 2015 at 16:58
  • $\begingroup$ That sounds great, I got the wrong interpretation. $\endgroup$
    – millise
    Jan 25, 2015 at 1:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .