Return to Answer

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} / \binom{n-w}{\delta n - i} \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} / \binom{n-w}{\delta n - i} \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.

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.

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} / \binom{n-w}{\delta n - i} \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} / \binom{n-w}{\delta n - i} \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$.} $$

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} / \binom{n-w}{\delta n - i} \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} / \binom{n-w}{\delta n - i} \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.

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} / \binom{n-w}{\delta n - i} \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} / \binom{n-w}{\delta n - i} \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 it follows from the result mentioned in the question that

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

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} / \binom{n-w}{\delta n - i} \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} / \binom{n-w}{\delta n - i} \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$.} $$