# Limit of sum of binomials

I'm trying to calculate the limit for the sum of binomial coefficients:

$$S_{n}=\sum_{i=1}^n \left(\frac{{n \choose i}}{2^{in}}\sum_{j=0}^i {i \choose j}^{n+1} \right).$$

Numerically it seems to converge rapidly to zero and I have asked at https://math.stackexchange.com/questions/608296/limit-of-sum-i-1n-left-fracn-choose-i2in-sum-j-0i-i-choose but with no replies.

I tried applying Stirling's approximation and also using the fact that ${n \choose i} \leq 2^n/\sqrt{n}$ but that does not work well as the resulting function tends to infinity.

Please accept my apologies if this turns out to have a simple solution.

By Stirling approximation for the central binomial coefficient, we have $$\sum_{j\le i}\binom ij^{n+1}\le(i+1)2^{i(n+1)}\left(\frac2{i\pi}\right)^{(n+1)/2},$$ hence $$S_n\le\frac n{2^{n-1}}+2\left(\frac2\pi\right)^{(n+1)/2}\sum_{i=2}^n\binom ni\frac{2^i}{i^{(n-1)/2}}.$$ Put $$c_i=\binom ni\frac{2^i}{i^{(n-1)/2}}.$$ For $i\ge2$, we have \begin{align*}\frac{c_{i+1}}{c_i}&=2\frac{n-i}{i+1}\left(1+\frac1i\right)^{-(n-1)/2}\\&\le2\frac{n-i}{i+1}\exp\left(-\frac{n-1}{2(i+1)}\right) =2\frac{n-i}{i+1}\exp\left(-\frac{n-i}{2(i+1)}-\frac{i-1}{2(i+1)}\right).\end{align*} Taking derivatives, we see that the function $f(x)=2xe^{-x/2}$ is maximized on $[0,+\infty)$ for $x=2$, and then it is decreasing. In particular, $f(x)\le12e^{-3}$ for $x\ge6$. Since $-(i-1)/2(i+1)=-1/2+O(1/n)$ for $i\ge n/7$, and $4e^{-3/2},12e^{-3}<9/10$, we obtain $$\frac{c_{i+1}}{c_i}\le\frac9{10}$$ for all $i$. Thus, $S_n$ is bounded by a geometric series, and specifically, \begin{align*} S_n&\le\frac n{2^{n-1}}+20\left(\frac2\pi\right)^{(n+1)/2}c_2\\ &\le\frac n{2^{n-1}}+40\left(\frac2\pi\right)^{(n+1)/2}\frac{n^2}{2^{(n-1)/2}}=O(n^2\pi^{-n/2}). \end{align*}
• For more precise asymptotics, the first two terms in the sum are of the order $n2^{n-1}$ and $n^22^{-n}$, and the rest is bounded by the argument I gave by $O(c_3(2/\pi)^{n/2})=O(n^3(2/3\pi)^{n/2})=o(2^{-n})$, hence $S_n\sim n^22^{-n}$. – Emil Jeřábek Dec 18 '13 at 14:49
• As I wrote in the first comment, the true bound is $S_n\sim n^22^{-n}$. – Emil Jeřábek Dec 18 '13 at 21:25