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.

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|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
add comment

1 Answer 1

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|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
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$. –  TMM Sep 9 '11 at 14:19
add comment

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.