How to show that $2 ^\binom{N}{2} \sim \exp(\frac{N^2}{2}\ln(2))$

Question

How can we show that:

$2 ^\binom{N}{2} \sim \exp(\frac{N^2}{2}\ln(2))$

for large N.

Answer 1

Just use the definition!

$$\binom{N}{2} = \frac{N!}{2!(N-2)!} = \frac{N(N-1)}{2!} = \frac{N(N-1)}{2}$$

Now for $N\to\infty$ we can approximate $N(N-1) \approx N^2$ thence:

$$2^{\binom{N}{2}} \approx 2^{\frac{N^2}{2}}$$

Now we use the exponential representation, namely

$$a^b = e^{b\ln(a)}$$

And we get the desired result:

$$\large 2^{\frac{N^2}{2}} = e^{\frac{N^2}{2}\ln(2)}$$

Answer 2

$\binom{N}{2}=N(N-1)/2\approx N^2/2$. So $2^{\binom{N}{2}}=\exp(\binom{N}{2}\ln(2))\approx \exp(\frac{N^2}{2}\ln(2))$. Note that $N^2$ is in the exponent, not outside as you have written.

Answer 3

It's not actually true, for the usual meaning of $\sim$:

$$f(n)\sim g(n)\iff \lim_{n\to\infty} \frac{f(n)}{g(n)}=1$$

That's because $\exp(A\ln 2)=2^{A}$ so:

$$\dfrac{2^{\binom{N}2}}{\exp\left(\frac{N^2}{2}\ln 2\right)}=\dfrac{2^{\binom{N}{2}}}{2^{N^2/2}}=2^{-N/2}\to 0$$