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

I need to estimate the asymptotics of

$$\sum_{k=0}^{n} {\binom n k}^a, \quad a>2, \quad a \in \mathbb{N}$$

In particular, I'm pretty much interested in $a=4$ case, but if the general solution isn't very hard to produce and understand, I'd prefer general.

Possibly - could we somehow make use of fact that the most "heavy" members $k$ are located "near" $n/2\quad$ (e.g., $k=n/2 \pm o(\sqrt n)$)?

-

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}$$

-
Really beautiful indeed! – wh1t3cat1k Oct 22 '11 at 7:12
Could you please also add an 'for dummies' explanation of how the very first approximate equality works - I'm a little bit confused with $2^n$ with an integral here. – wh1t3cat1k Oct 22 '11 at 7:25
@wh1t3cat1k : I added a step ... and corrected an error. – leonbloy Oct 22 '11 at 11:40

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.

-
Good man! I don't think it's a problem of "Basics" as Concrete Mathematics categoried. – Frank Science Jun 8 '12 at 11:11