Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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