A couple of inequality / similarity that don't make sense to me.

Question

I was reading thru the proof for a combinatorics problem, but there were a couple places in there that gave me pause. In particular, one part of the proof had the following: $${n \choose t}\frac{2}{2^{t \choose 2}} \leq \frac{n^t}{t!} \frac{2}{2^{t \choose 2}} $$ (where $n$ is some arbitrarily large number and $t=2log_2 n$)

Another part of it had the following similarity: $$\frac{2n}{(2log_2n)!} \approx \frac{2n}{({2log_2n}/{e})^{2log_2n}}$$

There was no explanation provided for either of the above. I'd appreciate any help.

Answer 1

What you're seeing is that$\frac{n!}{(n-t)!}$ is best understood as having $n$ terms above and $n-t$ of those are cancelled by the denominator. So this expression is a product of $t$ terms all of which are less than $n$. Hence $\frac{n!}{(n-t)!}\leq n^t$ and so $\binom n t =\frac{n!}{(n-t)!t!}\leq \frac{n^t}{t!}$.

The second similarity is by the Sterling approximation.

Answer 2

The first one is easy. If you compare the two sides, it's really just asserting that $${n\choose t} \leq\frac{n^t}{t!}$$

But that follows quickly from the fact that $${n\choose t}=\frac{n!}{t!(n-t)!}=\frac{\overbrace{n(n-1)(n-2)\cdots(n-t+1)}^{t{\textrm{ factors}}}}{t!}$$ since each of the factors in the last numerator are no more than $n$.