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

#### Solutions Collecting From Web of "Limit of $\sum_{i=1}^n \left(\frac{{n \choose i}}{2^{in}}\sum_{j=0}^i {i \choose j}^{n+1}\right)$"

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

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

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