Is $ \lim_{n \to \infty} \sum_{k=1}^{n-1}\binom{n}{k}2^{-k(n-k)} = 0$?

Question

Is it true that:

$$ \lim_{n \to \infty} \sum_{k=1}^{n-1}\binom{n}{k}2^{-k(n-k)} = 0 \;?$$

It seems true numerically, but how can this limit be shown?

Answer 1

Note that $(n-k)$ is at least $n/2$ for $k$ between 1 and $n/2$. Then, looking at the sum up to $n/2$ and doubling bounds what you have above by something like:

$$\sum_{k=1}^{n-1}\binom{n}{k}2^{-kn/2}=\left(1+2^{-n/2}\right)^n-2^{-n/2}-1$$

which bounds your sum above and goes to zero.

Alternatively, use the bound

$$\binom{n}{k}\leq \frac{n^k}{k!}\;.$$

Since the sum is symmetric around $k=n/2$, work with the sum up to $n/2$. Then $n^k2^{-k(n-k)}=2^{k(\log_2 n-n+k)}$. For $k$ between 1 and $n/2$ and for large $n$ this scales something like $2^{-kn/2}$, which when summed from 1 to $n/2$ in $k$ will tend to 0 as $n\rightarrow\infty$.