# A combinatorial inequality

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.

-
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

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.

-

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 .

-

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.

-