Asymptotics of $\sum_{k=0}^{n} {\binom n k}^a$

Solution 1:

A quick way to get the leading term is to use the fact that ${n \choose k}/2^n$ represents a Binomial(n,1/2), which for large $n$ approximates a normal with $\mu=n/2$ and $\sigma^2=n/4$

So $$ {\binom n k} \approx 2^{n} \frac{1}{\sqrt{2 \pi \sigma^2}} \exp\left(-\frac{(k-\mu)^2}{2 \sigma^2}\right) $$

and $$\sum_{k=0}^{n} {\binom n k}^a \approx 2^{a n} \int \left( \frac{1}{\sqrt{2 \pi \sigma^2}} \exp\left(-\frac{(x-\mu)^2}{2 \sigma^2}\right)\right)^a dx = $$

$$ = 2^{an} \frac{1}{(2 \pi \sigma^2)^{a/2}} \int \exp\left(-\frac{(x-\mu)^2}{2 \sigma_1^2}\right) dx$$

with $\sigma_1^2=\sigma^2/a = n/(4a)$

So we get

$$ 2^{an} \frac{1}{(2 \pi \sigma^2)^{a/2}} (2 \pi \sigma_1^2)^{1/2} = \frac{2^{an}}{a^{1/2}} \left( \frac{\pi n}{2}\right)^{(1-a)/2} $$

Solution 2:

Problem 9.18 in Concrete Mathematics, 2nd edition, says $$\sum_{k=0}^{2n} \binom{2n}{k}^{\alpha} = 2^{2 n \alpha} (\pi n)^{(1-\alpha)/2} \alpha^{-1/2} \left(1 + O(n^{-1/2+3\epsilon})\right).$$

The derivation for the $\alpha = 1$ case (which, of course, we already know!) is given in detail as the last example in Chapter 9. It's three pages long, so I won't try to reproduce it here, but it can be adapted to give this result.

Here's an outline of the argument, though. Replace $n$ with $n+k$ to get $\sum_k \binom{2n}{n+k}^{\alpha}$. Now the dominant terms in the sum are those for values of $k$ near $0$. Split the sum into parts with $|k| \leq n^{1/2+\epsilon}$ and $|k| > n^{1/2+\epsilon}$. For the first sum, use Stirling's approximation. You'll also eventually need to estimate $\sum_k e^{-k^2 \alpha/n}$, which is approximately $\int_{-\infty}^{\infty} e^{-x^2 \alpha/n} dx = \sqrt{\frac{\pi n}{a}}$. The second sum turns out to be negligible compared to the first sum.