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

Solution 1:

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

Solution 2:

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