Asymptotics of ${2^n \choose n}$?

Question

How can one compute the asymptotics of ${2^n \choose n}$? I know it is bounded below and above by $\left(\frac{2^{n}}{n}\right)^n$ and $\left(\frac{2^{n}e}{n}\right)^n$.

If I plug in Stirling's approximation I get

$$\frac{2^{2^n n+n/2-1/2}}{(2^n-n)^{2^n-n+1/2} n^{n+1/2}\sqrt{\pi}}.$$

I am hoping there is a simpler asymptotic formulation and in particular I would like to compare it to $2^{n^2}$.

Answer 1

Writing a product as the exponential of the sum of the logarithms is often a fruitful method.

Here we can write

$$\begin{align} \binom{2^n}{n} &= \prod_{m=1}^n \frac{2^n - (m-1)}{m}\\ &= \frac{2^{n^2}}{n!} \prod_{k=1}^{n-1} \left(1- \frac{k}{2^n}\right)\\ &= \frac{2^{n^2}}{n!} \exp \left(\sum_{k=1}^{n-1} \log \left(1-\frac{k}{2^n} \right)\right)\\ &= \frac{2^{n^2}}{n!} \exp \left(-\frac{n(n-1)}{2^{n+1}} + O\left(\frac{n^3}{2^{2n}}\right)\right) \end{align}$$

to obtain an expression that allows good bounds. We have the first result

$$\binom{2^n}{n}\sim \frac{2^{n^2}}{n!}$$

by recognising that $\exp \left(- \frac{n^2}{2^n}\right)$ can be reasonably approximated by $1$, and using Stirling's approximation for the factorial, we can write that as

$$\binom{2^n}{n} \sim \frac{1}{\sqrt{2\pi n}}\left(\frac{2^ne}{n}\right)^n.$$

Using some terms of the approximation of the logarithms, more precise expressions can be obtained, e.g.

$$\binom{2^n}{n} \approx \frac{2^{n^2}}{n!} \left(1 - \frac{n(n-1)}{2^{n+1}}\right)$$

by approximating $\log (1-x) \approx -x$ for small $x$.

Answer 2

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}% \newcommand{\dd}{{\rm d}}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\fermi}{\,{\rm f}}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\half}{{1 \over 2}}% \newcommand{\ic}{{\rm i}}% \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\ol}[1]{\overline{#1}}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ With $N \gg n \gg 1$: \begin{align} {N \choose n} &\approx {\root{2\pi}N^{N + 1/2}\expo{-N} \over \bracks{\root{2\pi}n^{n + 1/2}\expo{-n}}\bracks{\root{2\pi}\pars{N - n}^{\pars{N - n} + 1/2}\expo{-\pars{N - n}}}} \\[3mm]&= {1 \over \root{2\pi}}\,{N^{N + 1/2} \over n^{n + 1/2}\pars{N - n}^{N - n + 1/2}} = {1 \over \root{2\pi}}\,{N^{n} \over n^{n + 1/2}\pars{1 - n/N}^{N - n + 1/2}} \\[3mm]&= {1 \over \root{2\pi n}}\,\pars{N \over n}^{n} \expo{-\pars{N - n + 1/2}\ln\pars{1 - n/N}} \\[3mm]&\approx {1 \over \root{2\pi n}}\,\pars{N \over n}^{n} \exp\pars{-\bracks{N - n + \half}\pars{-\,{n \over N}}} \approx {1 \over \root{2\pi n}}\,\pars{N \over n}^{n} \exp\pars{n - {n^{2} \over N}} \end{align}

With $N \equiv 2^{n} \gg n \gg 1$: $$\color{#0000ff}{\large% {2^{n} \choose n} \approx {1 \over\root{2\pi n}}\pars{2^{n}\expo{} \over n}^{n}\exp\pars{-2^{-n}\,n^{2}}} $$