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.
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.
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.