13
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\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.