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 can I prove $$ \log \binom nk \leq k \left(1 +\log\frac{n}{k}\right) $$

where $\binom\cdot\cdot$ stands for combination.

I tried to use stirling approximation but I couldn't get the inequality.

share|improve this question
1  
Even if stirling approximation would of helped it would not show the claim since it talks about small $n$-s as well. I suggest raising in power of 2 (eliminating the log). then I would try to find a combinatorical problem such that would help (LHS - it's easy to find combinatorical meaning, RHS - something of the form "two options and for every option there are two optsions thus $2*2*...$). Hope this helps –  Belgi Apr 16 '12 at 14:49
add comment

2 Answers 2

up vote 2 down vote accepted

By exponentiation on both sides, what we basically have to prove is that $\binom nk \le (\frac {en} {k})^k$. This is true for $k = 1$ as $n \le en$ (the $k = 0$ case does not make sense because of $\log 0$). Now suppose this is true for $k$, we want to prove it is also true for $k + 1$. To do this take ratios. $$\binom n{k+1} / \binom n{k} = \frac{n-k}{k+1}\;.$$ On the other hand, $$\left(\frac {en} {k+1}\right)^{k+1} / \left(\frac {en} {k}\right)^k = \frac{n}{k+1} \times \frac{e}{(1+1/k)^k} \ge \frac{n}{k+1}$$ as $(1+1/k)^k \le e$. Also, $\frac{n}{k+1} \ge \frac{n-k}{k+1}$ obviously. So the RHS is increasing faster than the LHS at each step.

share|improve this answer
add comment

Hint :

Try to prove :

$$\binom {n}{k} \leq \frac{n^k}{k!} ~\text{ and } \frac{1}{k!} \leq \frac{e^k}{k^k}$$

using induction .

share|improve this answer
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.