Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How to prove:

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

The question also gives a hint : "Use induction on k ≤ n/2 to prove inequality". I tried but the got stuck at this step:

$$ 1 \leq (\frac{n}{n-1})^{(n-1)} \times (\frac {n - k - 1} { n - k }) ^ {n - k} $$

share|cite|improve this question
Yeah, n should be be on the top. – ablmf Sep 9 '11 at 2:09
I also think it should be $k$, not $n$ in the first term on the right in the second inequality. But I get stuck the same place. – Ross Millikan Sep 9 '11 at 2:12
I did the induction on n, not k, so the first term is different. I also tried induction on k, also failed. – ablmf Sep 9 '11 at 2:18
up vote 4 down vote accepted

A proof by induction on $n$, instead of $k$, does work. Suppose that the inequality holds for certain $n$. Then for $n + 1$ we want to prove the marked inequality below.

$$\binom{n+1}{k} = \frac{n+1}{n-k+1} \binom{n}{k} \leq \frac{n+1}{n-k+1} \cdot \frac{n^n}{k^k (n - k)^{(n - k)}} \stackrel{?}{\leq} \frac{(n+1)^{n+1}}{k^k (n - k + 1)^{(n - k + 1)}}$$

Rewriting this marked inequality gives

$$\left(\frac{n-k+1}{n-k}\right)^{n-k} \stackrel{?}{\leq} \left(\frac{n+1}{n}\right)^{n}$$

Writing $n - k = m < n$, we get

$$\left(1 + \frac{1}{m}\right)^m \stackrel{?}{\leq} \left(1 + \frac{1}{n}\right)^n$$

Since $f(x) = (1 + \frac{1}{x})^x$ is increasing in $x$ (with limit value $e$) the result then follows.

share|cite|improve this answer
The how to show that $(1 + \frac 1 x ) ^ x $ is increasing, by calculating derivative? – ablmf Sep 9 '11 at 13:06
Yes. First you can write $f(x) = e^{x \ln((x+1)/x)}$, so that $f'(x) = f(x) \cdot (\ln(1 + \frac{1}{x}) - \frac{1}{x+1}) = f(x) \cdot g(x)$. For $g(x)$ getting the sign is not so easy, but calculating another derivative gives $g'(x) = -1/(x(x+1)^2)$. So $g'(x)$ is decreasing in $x$ for positive $x$, while $\lim_{x \to \infty} g(x) = 0$. So $g(x) > 0$ for all positive $x$, and therefore $f'(x) = f(x) g(x) > 0$ for all positive $x$. So $f(x)$ is increasing in $x$. – TMM Sep 9 '11 at 14:19

Your Answer


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.