Surprising approximation of weighted sum of binomial coefficients

The following sum appeared in connection to the problem addition of angular momentum in physics:

$$\frac{1}{2^{n+3}}\sum_{k=0}^n \left(\frac{n-2k-1}{\sqrt{k+1}}+\frac{n-2k+1}{\sqrt{n-k+1}}\right)^2 {n\choose k}$$

The intriguing thing about this sum is extremely well approximated by $1-\frac{c}{n}$, where $c$ is some constant when $n\to\infty$. I wonder if there is a simple way to see this, or to get this lower bound by carefully approximating this rather unappealing sum.

-

1 Answer

Notice that the sum can be given a probabilistic interpretation, since $\frac{1}{2^n} \binom{n}{k}$ is the point mass function of a symmetric Binomial random variable.

Let $X \sim \operatorname{Binom}\left(n, \frac{1}{2}\right)$. Then the sum in question equals $$S = \frac{1}{8} \mathbb{E} \left( \left( \frac{n-2X -1}{\sqrt{X+1}} + \frac{n-2X +1}{\sqrt{n-X+1}} \right)^2 \right)$$ In the large $n$ limit, the de Moivre-Laplace theorem can be used, and $X$ can be approximated in distribution as $\frac{n}{2} + \frac{\sqrt{n}}{2} Z$, where $Z$ is the standard normal variable.

The sum $S$ then approximately equals: $$S \approx \frac{1}{8} \mathbb{E}\left( \left( \sqrt{2}\frac{1+\sqrt{n} Z}{\sqrt{2+n + \sqrt{n} Z}} + \sqrt{2}\frac{-1+\sqrt{n} Z}{\sqrt{2+n - \sqrt{n} Z}} \right)^2 \right) = \mathbb{E}\left( Z^2 + \frac{3}{4n} Z^2 \left( Z^2-4\right) + \mathcal{o}\left(\frac{1}{n}\right) \right) = 1 - \frac{3}{4 n} + \mathcal{o}\left(\frac{1}{n}\right)$$ where $\mathbb{E}(Z^{2k}) =(2k-1)!!$ was used, in particular $\mathbb{E}(Z^{2}) =1$ and $\mathbb{E}(Z^{4}) = 3$.

Added: The series expansion is derived using simple algebra: $$\begin{eqnarray} \frac{\pm 1 + \sqrt{n} Z}{\sqrt{2+n \pm \sqrt{n} Z}} &=& \frac{Z \pm \frac{1}{\sqrt{n}}}{\sqrt{1 + \frac{2}{n} \pm \frac{Z}{\sqrt{n}}}} \\ &=& \left( Z \pm \frac{1}{\sqrt{n}} \right) \left( 1 - \frac{1}{2} \left(\frac{2}{n} \pm \frac{Z}{\sqrt{n}} \right) + \frac{3}{8} \left(\frac{2}{n} \pm \frac{Z}{\sqrt{n}} \right)^2 + \mathcal{o}\left(\frac{1}{n} \right) \right) \\ &=& \left( Z \pm \frac{1}{\sqrt{n}} \right) \left( 1 \mp \frac{Z}{2 \sqrt{n}} + \frac{3 Z^2}{8 n} + \mathcal{o}\left(\frac{1}{n} \right) \right) \\ &=& Z \mp \frac{Z^2-2}{2 \sqrt{n}} + \frac{3 Z (Z^2-4)}{8n} + \mathcal{o}\left(\frac{1}{n} \right) \end{eqnarray}$$

-
Very nice observation indeed! Beautifully concise. – Alex Lomachenko May 17 '12 at 14:25
I don't see how you get the last line so quickly without going through the messy calculation. – Alex Lomachenko May 18 '12 at 14:22
@AlexLomachenko The series expansion is not that messy, I have expanded the post. – Sasha May 18 '12 at 15:58