3
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$ Mar 13, 2012 at 22:15
  • $\begingroup$ 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.) $\endgroup$ Mar 13, 2012 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.