I today see a approximated equation, when $n \ll u $:
$\log {u \choose n} \approx n \Big(\log \frac{u}{n} + 1.44\Big)$
I would like to know how to prove it.
I today see a approximated equation, when $n \ll u $:
$\log {u \choose n} \approx n \Big(\log \frac{u}{n} + 1.44\Big)$
I would like to know how to prove it.
It looks like pedja has pointed you in the right direction here. On Wikipedia there's the bounds: \begin{align*} {u \choose n} &= \frac{1}{n!} u(u-1)\cdots(u-n+1) \\ & \leq \frac{u^n}{n!} \\ & \leq \left(\frac{u\ e}{n}\right)^n \end{align*} since $n! \geq \left(\frac{n}{e}\right)^n$, and \begin{align*} {u \choose n} & = \frac{u}{n} \cdot \frac{u-1}{n-1} \cdots \frac{u-n+1}{1} \\ & \geq \left(\frac{u}{n}\right)^n. \end{align*}
By taking $\log_2$ of both sides of these bounds, we obtain \[n \log_2 \frac{u}{n} \leq \log_2 {u \choose n} \leq n \left(\log_2 \frac{u}{n}+\log_2 e\right),\] where $\log_2 e$ is approximately $1.44$.
If $n=o(\log u)$, then \[\log_2 {u \choose n} \sim n \log_2 \frac{u}{n},\] so the $1.44$ won't be necessary.