Limit of $\sum_{i=1}^n \left(\frac{{n \choose i}}{2^{in}}\sum_{j=0}^i {i \choose j}^{n+1}\right)$ 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).$$
 A: For $p\ge2$, Hölder says
$$
\|f\|_p^p\le\|f\|_2^2\,\|f\|_\infty^{p-2}\tag{1}
$$
and we know that
$$
\sum_{j=0}^i\binom{i}{j}^2=\binom{2i}{i}\tag{2}
$$
and
$$
\binom{i}{j}\le\binom{i}{i/2}\tag{3}
$$
For odd $i$, use $\binom{i}{i/2}=\binom{i}{(i\pm1)/2}=\frac12\binom{i+1}{(i+1)/2}$.
Applying $(1)$ to $(2)$ and $(3)$ and using $\binom{2n}{n}\le\frac{4^n}{\sqrt{\pi n}}$ yields
$$
\begin{align}
\sum_{j=0}^i\binom{i}{j}^{n+1}
&\le\binom{2i}{i}\binom{i}{i/2}^{n-1}\\
&\le\frac{4^i}{\sqrt{\pi i}}\left(\frac{2^i}{\sqrt{\pi i/2}}\right)^{n-1}\\
&=\frac{2^{in+n/2+i-1/2}}{(\pi i)^{n/2}}\tag{4}
\end{align}
$$
Apply $(4)$ and note that for $i\ge6$, we have $\sqrt{\frac{2}{\pi i}}\le\frac1{\sqrt{3\pi}}\lt\frac13$
$$
\begin{align}
S_{n}
&=\sum_{i=1}^n\left(\frac{\binom{n}{i}}{2^{in}}\sum_{j=0}^i\binom{i}{j}^{n+1}\right)\\
&\le\frac1{\sqrt2}\sum_{i=1}^n\left(\frac2{\pi i}\right)^{n/2}2^i\binom{n}{i}\\
&\le\frac1{\sqrt2}\sum_{i=1}^5\left(\frac2{\pi i}\right)^{n/2}2^i\binom{n}{i}
+\frac1{\sqrt2}\sum_{i=6}^n\left(\frac1{\sqrt{3\pi}}\right)^n2^i\binom{n}{i}\\
&\le\frac1{\sqrt2}\sum_{i=1}^5\left(\frac2{\pi i}\right)^{n/2}2^i\binom{n}{i}
+\frac1{\sqrt2}\left(\frac{3}{\sqrt{3\pi}}\right)^n\tag{5}
\end{align}
$$
Each of the $6$ terms in $(5)$ decays exponentially to $0$.
A: Simply multiplying the largest term by the number of terms in the sum yields
$$
\begin{align}
\frac{\binom{n}{i}}{2^{in}}\sum_{j=0}^i\binom{i}{j}^{n+1}
&\le(i+1)\binom{i}{i/2}\binom{n}{i}\left(\binom{i}{i/2}2^{-i}\right)^n\tag{1}
\end{align}
$$
using $\binom{i}{i/2}=\binom{i}{(i\pm1)/2}=\frac12\binom{i+1}{(i+1)/2}$ for odd $i$.
Since $\sum\limits_{j=0}^i\binom{i}{j}=2^i$, we know that
$$
\binom{i}{i/2}\le2^i\tag{2}
$$
Furthermore, $\binom{i}{i/2}2^{-i}$ is non-increasing:
$$
\begin{align}
\binom{2k-1}{k-1}2^{-2k+1}
&=\binom{2k}{k}2^{-2k}\\[6pt]
&=\frac{2k+2}{2k+1}\binom{2k+1}{k+1}2^{-2k-1}\\[6pt]
&\gt\binom{2k+1}{k+1}2^{-2k-1}\tag{3}
\end{align}
$$
Note that
$$
\sum\limits_{i=0}^n(i+1)\ 2^i\,\binom{n}{i}=\frac{2n+3}{3}3^n\tag{4}
$$
Combining $(1)$, $(2)$, $(3)$, and $(4)$ yields
$$
\begin{align}
\sum_{i=k}^n\frac{\binom{n}{i}}{2^{in}}\sum_{j=0}^i\binom{i}{j}^{n+1}
&\le\sum_{i=k}^n(i+1)\binom{i}{i/2}\binom{n}{i}\left(\binom{i}{i/2}2^{-i}\right)^n\\
&\le\sum_{i=k}^n(i+1)\ \quad2^i\quad\binom{n}{i}\left(\binom{i}{i/2}2^{-i}\right)^n\\
&\le\frac{2n+3}{3}3^n\left(\binom{k}{k/2}2^{-k}\right)^n\tag{5}
\end{align}
$$
Applying $(5)$ with $k=23$ gives
$$
\begin{align}
\sum_{i=23}^n\frac{\binom{n}{i}}{2^{in}}\sum_{j=0}^i\binom{i}{j}^{n+1}
&\le\frac{2n+3}{3}0.48354^n\\
&=o(2^{-n})\tag{6}
\end{align}
$$
For $i=1$,
$$
\frac{\binom{n}{i}}{2^{in}}\sum\limits_{j=0}^i\binom{i}{j}^{n+1}=\frac{2n}{2^n}\tag{7}
$$
For $i=2$,
$$
\frac{\binom{n}{i}}{2^{in}}\sum\limits_{j=0}^i\binom{i}{j}^{n+1}=\frac{n(n-1)/2}{4^n}\left(2+2^{n+1}\right)\sim\frac{n^2-n}{2^n}\tag{8}
$$
For $i\ge3$,
$$
\begin{align}
\frac{\binom{n}{i}}{2^{in}}\sum\limits_{j=0}^i\binom{i}{j}^{n+1}
&\le(i+1)\binom{i}{i/2}\binom{n}{i}\left(\binom{i}{i/2}2^{-i}\right)^n\\
&=O\left(n^4\left(\frac38\right)^n\right)\\[6pt]
&=o(2^{-n})\tag{9}
\end{align}
$$
because $\binom{n}{i}\le\frac{n^i}{i!}$ and for $i\ge5$, $\binom{i}{i/2}2^{-i}\lt\frac38$.
Thus, $(6)$, $(7)$, $(8)$, and $(9)$ show that
$$
S_n\sim\frac{n^2+n}{2^n}\tag{10}
$$
A: Let $$B(n,r)=\sum_{k=0}^{n}\binom{n}{k}^r\le \frac{2^{rn}}{\sqrt r}\left(\frac{2}{\pi n}\right)^{\frac{r-1}{2}}$$
so that for the sum $S_n$
$$
S_n=\sum_{i=1}^n \left[\binom{n}{i}2^{-in}\sum_{j=0}^i {i \choose j}^{n+1} \right]=\sum_{i=1}^n\binom{n}{i}2^{-in}B(i,n+1)\le \sum_{i=1}^n\binom{n}{i}\frac{2^{i}}{\sqrt{n+1}}\left(\frac{2}{\pi i}\right)^{\frac{n}{2}}
$$
Using the inequality $\binom{n}{i}\le \left(\frac{n e}{i}\right)^i$ we obtain
$$
\begin{align}
S_n &\le \frac{1}{\sqrt{n+1}}\left(\frac{2}{\pi}\right)^{\frac{n}{2}}\sum_{i=1}^n (2en)^i i^{-(i+n/2)}\\
&=\frac{1}{\sqrt{n+1}}\left(\frac{2}{\pi}\right)^{\frac{n}{2}}\left[(2en)+\underbrace{(2en)^2 2^{-(2+n/2)}+\cdots+(2en)^n n^{-(3n/2)}}_{\to 0\,\text{for }n\to \infty}\right]
\end{align}
$$
and the we have
$$
S_n \le \frac{1}{\sqrt{n+1}}\left(\frac{2}{\pi}\right)^{\frac{n}{2}}(2en)\to 0\qquad\text{for }n\to\infty.
$$
