5
$\begingroup$

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?

1 Answers 1

3

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

  • 0
    @BrianM.Scott: Whoops! Let me try to correct.2012-12-03