Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Could you please help me with any method of solving this?

// Added later:

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)$)?

share|improve this question
add comment

2 Answers

up vote 8 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
Good man! I don't think it's a problem of "Basics" as Concrete Mathematics categoried. –  Frank Science Jun 8 '12 at 11:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.