Calculating $\sum_{k=0}^{n} {n\choose k} \sqrt{k}$

Question

I am trying to calculate the following expression but not sure how this can be solved yet. $$\sum_{k=0}^{n} {n\choose k} \sqrt{k}$$ The wiki page (https://en.wikipedia.org/wiki/Binomial_coefficient) contains a similar expression with $\sqrt{k}$ replaced by $k$ or $k^2$. If the above expression can be solved, I also wonder if we can solve it for any $k^j$ with any real number $j>0$?

Answer 1

For asymptotics, one might call for Watson's lemma. Using $\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$ for $n,k>0$, our sum is $$S_n=n\sum_{k=1}^n\binom{n-1}{k-1}\frac{1}{\sqrt{k}}=\frac{n}{\sqrt\pi}\sum_{k=1}^n\binom{n-1}{k-1}\int_0^\infty e^{-kx}\frac{dx}{\sqrt{x}}=\frac{n}{\sqrt\pi}\int_0^\infty(1+e^{-x})^{n-1}\frac{e^{-x}}{\sqrt{x}}\,dx$$ and, substituting $1+e^{-x}=2e^{-t}$, we get $$S_n=\frac{2^n n}{\sqrt{2\pi}}\int_0^{\log2}t^{-1/2}e^{-nt}\phi(t)\,dt,\quad\phi(t)=\left(\frac{-2t}{\log(2e^{-t}-1)}\right)^{1/2}.$$ Now the expansion $\phi(t)=1-\dfrac{t}{4}-\dfrac{5t^2}{32}-\dfrac{47t^3}{384}-\dfrac{237t^4}{2048}-\ldots$ gives, by the lemma, $$S_n\asymp 2^n\sqrt\frac{n}{2}\left(1-\frac{1}{8}n^{-1}-\frac{15}{128}n^{-2}-\frac{235}{1536}n^{-3}-\frac{24885}{32768}n^{-4}-\ldots\right)\quad(n\to\infty)$$

Answer 2

Let $X$ be a binomial random variable, with $n$ trials and probability $1/2$. Your expression is exactly $2^nE[X^j]$. Using the central limit theorem, for large $n$, $X$ is well approximated by $\frac{\sqrt{n}}2Z+\frac{n}2$, where $Z$ is a standard normal random variable. I will then use the approximation \begin{align} E[X^j] &\approx E\left[\left(\frac{\sqrt{n}}2Z+\frac{n}2\right)^j\right]\tag 1 \end{align} to get an approximation for $E[X^j]$. I am not at this time able to quantify the error of the approximation in $(1)$, which is necessary to determine how good of an approximation the final answer is. \begin{align} 2^nE[X^j] &\approx 2^nE\left[\left(\frac{\sqrt{n}}2Z+\frac{n}2\right)^j\right] \\& =2^{n}(n/2)^jE\left[(1+Z/\sqrt{n})^j\right] \\&\stackrel{1}=2^{n}(n/2)^j\sum_{i=0}^\infty \binom{j}{i}E[Z^i]n^{-i/2} \\&\stackrel{2}=\boxed{2^{n}(n/2)^j\sum_{i=0}^\infty \binom{j}{2i}(2i-1)!!\cdot n^{-i}} \end{align}

• In $1$, we use the Taylor series for $f(x)=(1+x)^j=\sum_{i\ge 0}\binom{j}ix^i$, where the binomial coefficient is defined for non-integer $j$ as $$\binom{j}i=\frac{j(j-1)\cdots(j-i+1)}{i!}.$$
• In $2$, we reindex $i\gets 2i$, and use the known moments of the standard normal random variable.

We can then further approximate by only taking the first several terms of the infinite summation. For example, when $j=1/2$, you get $$ \sum_{k=0}^n \binom{n}kk^{1/2}=2^nE[X^{1/2}]\approx 2^n(n/2)^{1/2}\left(1-\frac18n^{-1}-\frac{15}{128}n^{-2}-\dots\right), $$ so that $$ \sum_{k=0}^n \binom{n}kk^{1/2}\approx 2^n(n/2)^{1/2}(1+O(1/n)) $$ Again, use this with caution, because the goodness of this approximation depends on the the quality of the approximation $(1)$, which I am not able to quantify.