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 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|cite|improve this question
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
up vote 3 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|cite|improve this answer

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|cite|improve this answer

I realize I'm late but here's an asymptotic approach:

Since $\binom{n}{k} < \frac{n^k}{k!}$, the LHS is upper-bounded by $\log \frac{n^k}{k!} = n \log k + \sum_{j=1}^{k} \log j$. The second sum can be approximated using Euler-Maclaurin formula, but just a corresponding integral will do: $$ \sum_{j=1}^{k} \log j < 1 +\int_{1}^{k} \log x dx = k \log k -k < k \log k $$

so the LHS is upperbounded by $n \log \frac{n}{k}$, which is clearly less than the RHS.

share|cite|improve this answer

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.