# How to get this upper bound of combinations?

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

-
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

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.

-
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