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.



(Asymptotics of) Sum involving alternating sign Chu-Vandermonde
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.


