(Asymptotics of) Sum involving alternating sign Chu-Vandermonde

Question

While considering eigenvalues of a certain Cayley graph, I came across the following sum: $$\sum_{r=0}^{d}\sum_{i=0}^{r} (-1)^{i} \binom{w}{i}\binom{n-w}{r-i}$$ where $d$, $w$, and $n$, are all positive integers, $0\leq w \leq n$ and $0\leq d\leq n$. Is there a way to find the asymptotics of this sum for large $n$, and $d=\delta n$ with $0\leq \delta\leq n$ a constant fraction?

The inner sum is a Chu-Vandermonde with alternating signs. Without the alternating sign, the sum may be approximated by $2^{nH(d/n)}$ (up to some other minor factors), where $H$ is the binary entropy function.

Any help will be appreciated.

Thanks in advance.

Answer 1

Let $S_d$ be the sum in the question. The inner summand $\sum_{i=0}^r (-1)^i \binom{w}{i} \binom{n-w}{r-i}$ is the coefficient of $x^r$ in $(1-x)^w(1+x)^{n-w}$. Hence $S_d$ is the coefficient of $x^d$ in $(1-x)^{w-1}(1+x)^{n-w}$ and so

$$ S_d = \sum_{i=0}^d (-1)^i \binom{w-1}{i}\binom{n-w}{d-i} $$

which is the $d$th inner summand for $w-1$ and $n-1$. (This cancellation is expected, because $\sum_{i=0}^r (-1)^i \binom{w}{i}$ is the $w$th iterated difference operator.)

For the asymptotics, observe that if $0 \le i \le w$ then

$$ \binom{c}{b-i} / \binom{c}{b} \in \left( \left(\frac{b-w}{c-b+w}\right)^i, \left( \frac{b}{c-b} \right)^i \right). $$

Applying this with $c = n-w$ and $b = \delta n$ we get

$$ \binom{n-w}{\delta n-i} / \binom{n-w}{\delta n } \in \left( \left( \frac{\delta-w/n}{1-\delta}\right)^i , \left(\frac{\delta}{1-\delta-w/n}\right)^i \right). $$

It follows that

$$ \binom{n-w}{\delta n-i} / \binom{n-w}{\delta n } \rightarrow \left(\frac{\delta}{1-\delta}\right)^i \quad \text{as $n \rightarrow \infty$}, $$

uniformly for $i$ such that $0\le i \le w$. When $\delta n \ge w$ the sum over $i$ in the expression for $S_{\delta n}$ above can be replaced with a fixed finite sum from $0$ to $w$, so

$$ S_{\delta n} \sim \binom{n-w}{\delta n} \sum_{i=0}^{w-1} (-1)^i \binom{w-1}{i} \left(\frac{\delta}{1-\delta}\right)^i = \binom{n-w}{\delta n} \left(\frac{1-2\delta}{1-\delta}\right)^w. $$

A similar argument shows that

$$ \binom{n-w}{\delta n} / \binom{n}{\delta n} \sim (1-\delta)^w $$

and so $$ S_{\delta n} \sim (1-2\delta)^w \binom{n}{\delta n} \quad \text{as $n \rightarrow \infty$.} $$

In particular, $S_{\delta n} \le (1-2\delta)^w 2^{n H(\delta)}$ where $H$ is Shannon's entropy function. This bound is asymptotically correct after taking logs.