# Asymptotic Expansion for $\frac1{2^n}\sum_{k=1}^n\frac1{\sqrt{k}}\binom{n}{k}$

Prior Art

The fact that $$\lim_{n\to\infty}\frac1{2^n}\sum_{k=1}^n\frac1{\sqrt{k}}\binom{n}{k}=0\tag1$$ is the topic of this question. An argument using a bit of probability theory gives a first order estimate of the size of the sum.

Estimate of the Sum

The binomial distribution has mean $$\frac n2$$ and variance $$\frac n4$$, Chebyshev's Inequality says $$\frac1{2^n}\sum_{k=1}^n\binom{n}{k}\left[\left|k-\frac n2\right|\ge x\right]\le\frac n{4x^2}\tag2$$ Setting $$x=n^{7/8}$$ in $$(2)$$ gives $$\frac1{2^n}\sum_{k=1}^n\binom{n}{k}\left[\left|k-\frac n2\right|\ge n^{7/8}\right]\le\frac1{4n^{3/4}}\tag3$$ which means $$\frac1{2^n}\sum_{k=1}^n\binom{n}{k}\left[\left|k-\frac n2\right|\lt n^{7/8}\right]\ge1-\frac1{4n^{3/4}}\tag4$$ Note that when $$\left|k-\frac n2\right|\le n^{7/8}$$, $$\frac1{\sqrt{n/2+n^{7/8}}}\le\frac1{\sqrt{k}}\le\frac1{\sqrt{n/2-n^{7/8}}}\tag5$$ and the width of this interval is \begin{align} \frac1{\sqrt{n/2-n^{7/8}}}-\frac1{\sqrt{n/2+n^{7/8}}} &=\frac{\sqrt{n/2+n^{7/8}}-\sqrt{n/2-n^{7/8}}}{\sqrt{n^2/4-n^{7/4}}}\\ &=\frac{2n^{7/8}}{\sqrt{n^2/4-n^{7/4}}\left(\sqrt{n/2+n^{7/8}}+\sqrt{n/2-n^{7/8}}\right)}\\[6pt] &=O\!\left(n^{-5/8}\right)\tag6 \end{align} Thus, when $$\left|k-\frac n2\right|\le n^{7/8}$$, $$\frac1{\sqrt{k}}=\sqrt{\frac2n}+O\!\left(n^{-5/8}\right)\tag7$$ In any case, $$\frac1{\sqrt{k}}\le1$$.

Therefore, \begin{align} \frac1{2^n}\sum_{k=1}^n\frac1{\sqrt{k}}\binom{n}{k} &=\frac1{2^n}\sum_{k=1}^n\frac1{\sqrt{k}}\binom{n}{k}\left[\left|k-\frac n2\right|\le x\right]\\ &+\frac1{2^n}\sum_{k=1}^n\frac1{\sqrt{k}}\binom{n}{k}\left[\left|k-\frac n2\right|\ge x\right]\\ &=\left(\sqrt{\frac2n}+O\!\left(n^{-5/8}\right)\right)\left(1+O\!\left(n^{-3/4}\right)\right)\\[6pt] &+O(1)\,O\!\left(n^{-3/4}\right)\\[6pt] &=\sqrt{\frac2n}+O\!\left(n^{-5/8}\right)\tag8 \end{align}

Question

Using the approach above, it is hard to see how to get more terms of an asymptotic expansion. Chebyshev is not very precise and that might be a limitation. The Binomial distribution approaches a Normal distribution quite well and that might offer a better approach. Is there an approach that allows more terms of an asymptotic expansion to be determined?

The key idea is to use the Laplace transform $$\tfrac1{\sqrt{\pi}}\int_{\mathbb{R}_+}\exp(-xt)t^{-1/2}=\tfrac1{\sqrt{x}}$$

therefore, the sum in question (denoted by $$S_n$$) becomes, by the binomial theorem

$$2^n S_n=(1/\sqrt{\pi}) \int_0^{\infty} t^{-1/2}\left((\exp(-t)+1)^n-1\right)\underbrace{=}_{ibp}C_n\underbrace{\int_0^{\infty}\sqrt{t}e^{-t}(1+e^{-t})^{n-1}}_{I_n}$$

with $$C_n=2 n/\sqrt{\pi}$$. Now expand the $$\log(1+\exp(-t))$$ term around it maximum value at $$t=0$$ (Exercise: Justify this Laplace style argument)

$$I_n=2^{n-1}\int_0^{\infty}\sqrt{t}e^{-(n+1)t/2}\left(1+t^2(n+1)/8+o(nt^2) \right)$$

evaluating the Gaussians yields

$$I_n=\sqrt{2 \pi}2^{n-1}\left(\frac{1}{n^{3/2}}+\frac{3}{8 n^{5/2}}+o(n^{-5/2})\right)$$

or finally

$$S_n= C_n I_n/2^n =\frac{\sqrt{2}}{n^{1/2}}\left(1+\frac{3}{8 n}+o(n^{-1})\right)$$

of course this approch easily generalizes to higher orders ….

Preliminaries

Compute scaled even moments about the mean: \begin{align} a_m(n)\,2^n &=\sum_{k=0}^n(n-2k)^{2m}\binom{n}{k}\\ &=\sum_{k=0}^n(n-2k)^{2m-2}(n-2k)^2\binom{n}{k}\\ &=\sum_{k=0}^n(n-2k)^{2m-2}\left(n^2-4k(n-k)\right)\binom{n}{k}\\ &=n^2a_{m-1}(n)\,2^n-\sum_{k=0}^n(n-2k)^{2m-2}4k(n-k)\binom{n}{k}\\ &=n^2a_{m-1}(n)\,2^n-\sum_{k=0}^n(n-2k)^{2m-2}4n(n-1)\binom{n-2}{k-1}\\ &=n^2a_{m-1}(n)\,2^n-4n(n-1)\sum_{k=0}^{n-2}(n-2-2k)^{2m-2}\binom{n-2}{k}\\[9pt] &=\left[n^2a_{m-1}(n)-n(n-1)\,a_{m-1}(n-2)\right]2^n \end{align} Therefore, if $$a_m(n)=\frac1{2^n}\sum_{k=0}^n(n-2k)^{2m}\binom{n}{k}$$ Then, $$a_0(n)=1$$ and we have the recurrence $$a_m(n)=n^2a_{m-1}(n)-n(n-1)\,a_{m-1}(n-2)$$ Note that the odd moments vanish by symmetry: $$\frac1{2^n}\sum\limits_{k=0}^n(n-2k)^{2m+1}\binom{n}{k}=0$$. $$\begin{array}{l|l} m&a_m(n)\\\hline 0&1\\ 1&n\\ 2&n\,(3n-2)\\ 3&n\left(15n^2-30n+16\right)\\ 4&n\left(105n^3-420n^2+588n-272\right)\\ 5&n\left(945n^4-6300n^3+16380n^2-18960n+7936\right)\\ 6&n\left(10395n^5-103950n^4+429660n^3-893640n^2+911328n-353792\right) \end{array}$$

Rewriting $$k=\frac n2\left(1-\frac{n-2k}n\right)$$ and applying the Taylor Series for $$\frac1{\sqrt{1-x}}$$, we get an asymptotic expansion: \begin{align} \frac1{2^n}\sum_{k=1}^n\frac{\binom{n}{k}}{\sqrt{k}} &=\sqrt{\frac2n}\frac1{2^n}\sum_{k=1}^n\frac{\binom{n}{k}}{\sqrt{1-\frac{n-2k}n}}\\ &=\sqrt{\frac2n}\sum_{m=0}^\infty\frac{a_m(n)}{(4n)^{2m}}\binom{4m}{2m}\\ &=\sqrt{\frac2n}\left(1+\frac{3}{8n}+\frac{35n(3n-2)}{128n^4}+\frac{231n\left(15n^2-30n+16\right)}{1024n^6}\right)\\ &=\bbox[5px,border:2px solid #C0A000]{\sqrt{\frac2n}\left(1+\frac{3}{8n}+\frac{105}{128n^2}+\frac{2905}{1024n^3}+O\!\left(\frac1{n^4}\right)\right)} \end{align}
Numerical Check $$\scriptsize \begin{array}{c|c} n&\frac1{2^n}\sum\limits_{k=1}^n\frac1{\sqrt{k}}\binom{n}{k}&\bbox[5px,border:2px solid #C0A000]{\text{approximation}}&\text{difference}\\\hline 10&0.46820996577803234600&0.46892136089480697187&0.00071139511677462587\\ 100&0.14196370942989554885&0.14196368849406250476&2.093583304409\times10^{-8}\\ 1000&0.044738166872811399488&0.044738166872187952008&6.23447479\times10^{-13} \end{array}$$