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.



Limit of sum of binomials
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\*}


