The standard lower bound of $(\frac{n}{k})^k \leq$ ${n}\choose{k}$ gives $n^n \leq$ ${n^2}\choose{n}$, which is in simple enough form for my purposes, but I'm wondering if there is an almost as simple, tighter lower bound.
For example, there is the very good lower bound of $\frac{4^n}{2n} \leq$ ${2n} \choose {n}$, derived from the binomial expansion of $(1+1)^{2n}$, but the above inequality would give only $2^n \leq$ ${2n} \choose {n}$.
Is there some similar neat trick I can exploit for the binomial coefficient I'm interested in?
Best Answer
The cases of ${N}\choose{n}$ with $N=n^2$ and $N=n^2$ are not similar because $n=o(N)$ in the first, but $n=O(N)$ in the second. For the case $N=n^2$ we get from the standard two-sided bound: $$ n^n \leq {{n^2}\choose{n}}\leq (ne)^n, $$ so the two bounds are relatively closer because $(e/n)^n$ quickly decreases.
This said, rjlipton proved a better lower bound valid for $k\leq\sqrt{N}$, namely $$ \frac{N^k}{4k!} \leq {{N}\choose{k}}, $$ which gives $$ \frac{n^{2n}}{4n!} \leq {{n^2}\choose{n}}. $$ By the Stirling formula, the asymptotic is $\frac{n^{2n}}{4n!}\sim\frac{(ne)^n}{4\sqrt{2\pi n}}$, which is exponentially closer to the upper bound than $n^n$. Moreover, since $n!\leq e\sqrt{n}\left(\frac{n}{e}\right)^n$, the slightly worse lower bound without factorial is $$ \frac{(ne)^n}{4e\sqrt{n}} \leq {{n^2}\choose{n}}. $$ It can be improved somewhat by using sharper bounds for the Stirling approximation.
The proof is based on first noting that $$ {{N}\choose{k}}\geq\frac{N^k}{k!}\left(1-\frac{k-1}{N}\right)^{k-1}, $$ and then estimating $$ \left(1-\frac{k-1}{N}\right)^{k-1}\geq\left(1-\frac{1}{\sqrt{N}}\right)^{\sqrt{N}}\geq\frac14 $$ for $2\leq k\leq\sqrt{N}$. The $\frac14$ factor can be improved when $N$ is large (up to anything smaller than $\frac1e$).