1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ – Brendan McKay Apr 25 '18 at 2:52
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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