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

Solution 1:

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 ….

Solution 2:

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

Answer

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