# Weighted sum of binomials with $r$-th power of lower index

Given $r\in(0,1),$ what is the best upper (asymptotic) bound for the following expression $$S(n,r):=\sum_{k=0}^n{n\choose k}k^r?$$ Holder's inequality gives $S(n,r)\le 2^n(\frac{n}{2})^r$ but I guess this is not optimal. Is there any better estimation?

• I don't think your upper bound is correct. It says that the weighted average of $k^r$ in the sum is at most $(n/2)^r$. However $(n-k)^r\gt k^r$ for $k\lt n/2$ so in fact the weighted average of $k^r$ in the sum is greater than $(n/2)^r$. – Brendan McKay Apr 25 '18 at 2:52

## 3 Answers

Since the expression is ALMOST the $r$-th derivative of $(1+x)^n$ evaluated at $x=1,$ the asymptotic expression is $2^{n-r}n^r,$ which is, in fact, your upper bound.

Probably not. The expression is $2^n E( {Z_n^r})$ where $Z_n$ is the sum of n iid 0-1 valued r.v.s which are 1 with prob $\frac 12$. However, by the SLLN $\frac {Z_n} n \approx \frac 12$ so one expects $$E((\frac {Z_n} n )^r) \approx (\frac 12)^r$$ so your expression is also the asymptotics for the sum and probably can't be improved too much. If you want to translate this into analysis you would show that the biggest contribution to the sum comes from a smallish nbhd around $\frac n 2$.

I tried a rather naive approach: Replacing the binomial by its Gaussian approximation $${n \choose k} \rightarrow 2^{n} \sqrt{2 \over \pi n} \exp\left\{- {2 \over n}\left(k-{n\over 2}\right)^2\right\}$$ and replacing the sum by an integral with upper limit $\infty$ $$\sum_{k=0}^{n}\rightarrow \int_0^{\infty} dk$$ Fortunately Mathematica was able to solve the resulting integral in terms of confluent hypergeometric functions, $_1F_1$, $$S(n,r) \approx\pi^{-1/2} 2^{n-\frac{r}{2}-1} n^{r/2} \left[\Gamma \left(\frac{r+1}{2}\right) \, _1F_1\left(-\frac{r}{2};\frac{1}{2};-\frac{n}{2}\right)+ \sqrt{2 n} \ \Gamma \left(\frac{r}{2}+1\right) \, _1F_1\left(\frac{1-r}{2};\frac{3}{2};-\frac{n}{2}\right)\right]$$ This is a very good approximation for the original sum, though quite clumsy. To get the correction terms to $2^n(n/2)^r$ I expanded the $_1F_1$ for large negative arguments, see, e.g., http://functions.wolfram.com/07.20.06.0019.01.I dropped exponentially small contributions, $\propto e^{-n/2}$, and found $$S(n,r) = 2^n \left(n \over 2\right)^r \left(1 - \frac{r(1-r)}{2 n} - \frac{r(6-11 r+6 r^2-r^3)}{8 n^2}+ O(n^{-3})\right ) + O(e^{-n/2}).$$ Note, that the exact results $S(n,0)=2^n$ and $S(n,1)=2^n(n/2)$ seem to be preserved in the sense that all correcting terms vanish in these cases.