Approximate series behavior for n towards infinity using sterlings approximation

Question

I try to find an approximation for the series $S = \sum_{i=0}^n {{n \choose 2} \choose i}$ (A066383 on OEIS) of the form $S \sim \mathcal{O}(2^{\alpha \cdot N^2})$ for $n \to \infty$.

I tried the following, but did not succeed.

In my opinion, the largest term of $S$ is the one, when $i=N$ (since $i$ does not reach $\frac{{N \choose 2}!}{2}$): $$\frac{{N \choose 2}!}{N! \cdot ({N \choose 2} -N)!}$$

I then write $$e^{\ln \bigl( \frac{{N \choose 2}!}{N! \cdot ({N \choose 2} -N)!} \bigr)}$$ and use sterlings approximation $\ln x! \approx x \ln x$: $$e^{\frac{N(N-1)}{2} \cdot \ln (\frac{N(N-1)}{2}) - N \ln N - \bigl[ (\frac{N(N-1)}{2} -N) \bigr] \cdot \ln \bigl( \frac{N(N-1)}{2} -N \bigr)}$$ and at this point I am stuck and would be grateful for any advice.

Note: I read, that $S = 2^{1/2 (N - 1) N} - {1/2 (N - 1) N \choose N + 1} 2F1(1, -N^2/2 + (3 N)/2 + 1, N + 2, -1)$, where $2F1(a,b;c;x)$ is the hypergeometric function. But I have no experience with the hypergeometric function and therefore don't know, how the second term would scale in this case.

Thank you in advance

Answer 1

For a binomial coefficient ${n \choose k}$ where $n$ is much larger than $k$ Stirling's approximation is unnecessarily complicated and we can use the simpler upper and lower bounds

$$\frac{1}{ek} \left( \frac{e(n-k)}{k} \right)^k \le \frac{(n-k)^k}{k!} \le {n \choose k} \le \frac{n^k}{k!} \le \frac{1}{e} \left( \frac{en}{k} \right)^k$$

where we used the crude Stirling inequalities

$$e \left( \frac{k}{e} \right)^k \le k! \le ek \left( \frac{k}{e} \right)^k$$

in the denominators (ref). This gives

$$\frac{1}{en} \left( \frac{e(n-3)}{2} \right)^n \le {{n \choose 2} \choose n} \le \frac{1}{e} \left( \frac{e (n-1)}{2} \right)^n$$

so the entire sum is bounded by

$$\frac{1}{en} \left( \frac{e(n-3)}{2} \right)^n \le \sum_{i=0}^n {{n \choose 2} \choose i} \le \frac{n+1}{e} \left( \frac{e(n-1)}{2} \right)^n$$

which is already enough to show that the true rate of growth is

$$S_n = \exp(n \log n + (1 - \ln 2) n + O(\log n)).$$

Answer 2

Using Stirling approximation for the maximum value, we have

$$\log\Bigg[\binom{\frac{n(n-1)}{2} }{n} \Bigg]=n(\log (n)+1-\log (2))-\frac{1}{2} (\log (n)+4+\log (2\pi ))-\frac{5}{4 n}-\frac{4}{3 n^2}+O\left(\frac{1}{n^3}\right)$$ which is very accurate.

This leads to the asymptotics $$\frac 1 {e^2\sqrt {2\pi n}}\left(\frac{e n}2 \right)^n e^{-\frac{13}{6n} }$$ For $n >90 $, the relative error is less than $1$%.