# (Asymptotics of) Sum involving alternating sign Chu-Vandermonde

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.

-

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.

-
I may be mistaken, but you should have substituted the reciprocal, i.e., $$S_{\delta n}\sim\binom{n-w}{\delta n}\sum_{i=0}^{w-1}(-1)^i\binom{w-1}{i}\left(\frac{1-\delta}{\delta}\right)^i$$ Anyway, thanks for the quick answer! –  Moshe Schwartz Mar 13 '12 at 22:15
Thanks: I think the answer is right as it stands, but I twice typed $\binom{n-w}{\delta n} / \binom{n-w}{\delta n-i}$ when I meant its reciprocal. (I have corrected it in the latest version.) –  Mark Wildon Mar 13 '12 at 22:38