6
$\begingroup$

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.

  • 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 helps2012-04-16

3 Answers 3

5

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.

2

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 .

0

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.

  • 0
    But shouldn't we have $\log{\frac{n^k}{k!}}=k\log{n}-\sum_{j=1}^k \log{j}$? Then proving that this is at most the right-hand side would be equivalent to showing that $k\log{k}-k\le\sum_{j=1}^k \log{j}$. What am I missing here?2017-02-06