12
$\begingroup$

Let $k$ be a fixed positive number and $n$ an integer increasing to infinity. Then $$\sum_{\nu =0}^n \binom{n}{\nu}^k \sim \frac{2^{kn}}{\sqrt{k}} \left( \frac{2}{\pi n} \right)^{\frac{k-1}{2}}.$$ This is from Polya's Problems and Theorems in Analysis, Vol. 1, Part II, Problem 40. The proof provided in the book is too simple. It says details can be found in Jordan's Cours d'Analyse, Vol.2, 3rd Ed, pp. 218-221. However, I cannot find this edition online, and what's worse, there is not any English translations. Can anyone give a proof in detail?

$\endgroup$
  • $\begingroup$ To eliminate any ambiguity, $C_n^\nu = \binom{\nu}{n}=\frac{\nu !}{n!(\nu-n)!}?$ $\endgroup$ – Semiclassical Oct 16 '14 at 15:41
  • 2
    $\begingroup$ Well, as usual, $C_{n}^{\nu }=\left( \begin{matrix} n \\ \nu \\ \end{matrix} \right)=\frac{n!}{\nu !\cdot \left( n-\nu \right)!}$. $\endgroup$ – Eclipse Sun Oct 17 '14 at 5:04
  • 2
    $\begingroup$ @EclipseSun see here if this helps :) $\endgroup$ – r9m Oct 25 '14 at 20:45
  • $\begingroup$ Exercise 9.18 of Concrete Mathematics: A Foundation for Computer Science by Graham, Knuth, and Patashnik may be the answer you are looking for. $\endgroup$ – Clement C. Jul 23 '16 at 15:05
3
+50
$\begingroup$

That kind of asymptotics follows from the Central Limit Theorem. If we consider the binomial random variable $X=B(n,1/2)$ as the sum of $n$ independent Bernoulli trials, we have: $$\mathbb{E}[X]=\frac{n}{4}, \qquad \operatorname{Var}[X]=\frac{n}{4}$$ from which the approximation: $$\frac{1}{2^n}\binom{n}{n/2+r}\approx \sqrt{\frac{2}{n\pi}}\exp\left(-\frac{2r^2}{n}\right).\tag{1}$$ By considering the $k$-th power of both terms and summing over $r\in[-n/2,n/2]$ (the main contribute is clearly given by the central binomial coefficient and its neighbours) we get: $$\sum_{r=-n/2}^{n/2}\binom{n}{n/2+r}^k \approx 2^{kn}\left(\frac{2}{\pi n}\right)^{\frac{k}{2}}\sum_{r=-n/2}^{n/2}\exp\left(-\frac{2kr^2}{n}\right)\tag{2}$$ and the claim follows from approximating the last sum with: $$\int_{-\infty}^{+\infty}\exp\left(-\frac{2kx^2}{n}\right)\,dx = \sqrt{\frac{\pi n}{2k}}.\tag{3}$$

$\endgroup$
  • 4
    $\begingroup$ I know that (1) is correct, and from (2) I can derive (3). But I have problem to understand the validity to take $k$-th power of (1) and sum them up. Why is the asymptotic expression still valid after this operation? $\endgroup$ – Eclipse Sun Oct 19 '14 at 11:09
  • 1
    $\begingroup$ @EclipseSun Excellent reaction... :-) $\endgroup$ – Did Oct 19 '14 at 11:36
3
$\begingroup$

This is not an answer, but is too long for the usual comment format. I have access to the reference given in the OP, so I looked it up, but I was disappointed.

In those pages 218 to 221, C. Jordan nowhere considers sums $\sum_{\nu} \binom{n}{\nu}^k$ for $k$ other than $1$. The strongest result shown there is a form of the CLT : Jordan shows that for $p\in[0,1]$, if $(\lambda_{n})$ is an integer sequence such that $\frac{\lambda_n}{n^a}$ is bounded for some $a<1$, then

$$ \sum_{\nu=\frac{n}{2}-\lambda_n}^{\frac{n}{2}+\lambda_n} \binom{n}{\nu}p^\nu(1-p)^{n-\nu} \sim_{n\to+\infty} \frac{1}{\sqrt{2\pi p(1-p)n}} \int_{-\lambda_n}^{\lambda_n} e^{-\frac{x^2}{2p(1-p)n}}dx $$

The key ingredient of the proof is that as $\lambda_n$ is sufficiently small compared to $n$, we can use a Stirling approximation $\log(t!)\sim (t+\frac{1}{2})\log(t)-t+\frac{\log(2\pi)}{2}$ for all the integers $t$ we need.

The only way this can help in my view is that it suggests showing something like

$$ \sum_{\nu =0}^n \binom{n}{\nu}^k \sim \sum_{\nu =\frac{n}{2}-n^a}^{\frac{n}{2}+n^a}\binom{n}{\nu}^k $$

for some $a<1$ depending perhaps on $k$. That’s still a big "if".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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