3
$\begingroup$

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

  • 0
    I did the induction on n, not k, so the first term is different. I also tried induction on k, also failed.2011-09-09

1 Answers 1

4

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.

  • 1
    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$.2011-09-09