Binomial Sums: When Are They Non-Zero?

Hey guys! Ever been staring at a complex binomial sum and wondered, "When on earth is this thing not zero?" Well, you're in the right place. Today, we're diving deep into a specific type of sum that pops up in number theory: $

$$\sum_{i = 0}^n (-1)^i\binom{A}{i}\binom{B}{n-i} \neq 0$$

We're going to figure out for which natural numbers $A$ and $B$ this inequality holds true, given the condition that $1 \leq n \leq \left\lfloor \frac{A+B-1}{2}\right\rfloor$. This is a pretty cool problem because it connects different areas of combinatorics and number theory, and understanding when these sums are non-zero can unlock a bunch of other mathematical insights.

So, grab your favorite beverage, settle in, and let's unravel this mystery together. We'll start by breaking down the sum itself, exploring some foundational identities, and then we'll build up to the conditions on $A$ and $B$ that make our sum sing with a non-zero value. Trust me, by the end of this, you'll have a much better grasp on these fascinating binomial expressions. And who knows, maybe you'll even start spotting them in the wild!

Deconstructing the Sum: What's Under the Hood?

Alright, let's get real about the sum we're wrestling with: $

$$\sum_{i = 0}^n (-1)^i\binom{A}{i}\binom{B}{n-i}$$

This expression, my friends, is a beautiful example of a binomial convolution. It involves multiplying two binomial coefficients and summing them up. The $(-1)^i$ factor is what makes it a bit tricky and also quite powerful, often appearing in identities related to inclusion-exclusion principles or alternating sums. The binomial coefficient $\binom{n}{k}$, as you know, represents the number of ways to choose $k$ items from a set of $n$ items. Here, we're choosing $i$ items from a set of size $A$ and $n-i$ items from a set of size $B$, and we're summing these products up, but with a twist: the alternating sign.

Now, a very famous identity that looks suspiciously similar is Vandermonde's Identity, which states that $

$$\sum_{k=0}^r \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$$

Our sum has that extra $(-1)^i$ term, which means Vandermonde's Identity alone won't directly solve it. This alternating sum is actually related to the coefficient of $x^n$ in the expansion of $(1-x)^A (1+x)^B$ or similar generating functions. Specifically, the sum we're looking at is the coefficient of $x^n$ in the expansion of $(1-x)^A (1+x)^B$ if we were summing over all integers, but the finite nature of $A$ and $B$ and the specific form of the sum tie it to other combinatorial identities.

Let's consider the identity related to the coefficient of $x^n$ in $(1+x)^A (1-x)^B$. The coefficient of $x^n$ in $(1+x)^A$ is $\binom{A}{n}$. The coefficient of $x^n$ in $(1-x)^B$ is $(-1)^n \binom{B}{n}$. The coefficient of $x^n$ in the product of two series is the convolution of their coefficients. So, the coefficient of $x^n$ in $(1+x)^A (1-x)^B$ is $

$$\sum_{i=0}^n \binom{A}{i} (-1)^{n-i} \binom{B}{n-i}$$

This is almost our sum, but not quite. The sign is different. Our sum is $

$$\sum_{i = 0}^n (-1)^i\binom{A}{i}\binom{B}{n-i}$$

Let's try to manipulate this. We know that $\binom{m}{k} = \binom{m}{m-k}$. Also, we can use the identity $\binom{n}{k} = (-1)^k \binom{k-n-1}{k}$. This doesn't seem to simplify things immediately. However, there's a key identity that relates to alternating sums and binomial coefficients: The identity for the coefficient of $x^k$ in $(1-x)^A(1+x)^B$ is $\sum_{i=0}^k \binom{A}{i}(-1)^{k-i}\binom{B}{k-i}$.

Our sum is directly related to the coefficient of $x^n$ in the product of $(1-x)^A$ and $(1+x)^B$. Let's expand $(1-x)^A$ and $(1+x)^B$ using the binomial theorem:

$(1-x)^A = \sum_{i=0}^A \binom{A}{i} (-x)^i = \sum_{i=0}^A (-1)^i \binom{A}{i} x^i$

$(1+x)^B = \sum_{j=0}^B \binom{B}{j} x^j$

When we multiply these two series, the coefficient of $x^n$ is obtained by summing terms where the powers of $x$ add up to $n$. That is, we need $i+j=n$, or $j=n-i$. So, the coefficient of $x^n$ in $(1-x)^A (1+x)^B$ is:

$\sum_{i=0}^n \left( (-1)^i \binom{A}{i} \right) \left( \binom{B}{n-i} \right)

This is precisely our sum! So, our problem boils down to finding when the coefficient of $x^n$ in the expansion of $(1-x)^A (1+x)^B$ is non-zero, under the given constraints on $n$, $A$, and $B$.

Connecting to Known Identities and Simplifications

Now that we've established our sum is the coefficient of $x^n$ in $(1-x)^A (1+x)^B$, let's see if we can simplify this expression. We know that $(1-x)^A (1+x)^B = (1-x)^A (1+x)^A (1+x)^{B-A} = ((1-x)(1+x))^A (1+x)^{B-A} = (1-x^2)^A (1+x)^{B-A}$.

This form, $(1-x^2)^A (1+x)^{B-A}$, is much more manageable! Let's expand each part:

$(1-x^2)^A = \sum_{k=0}^A \binom{A}{k} (-x^2)^k = \sum_{k=0}^A (-1)^k \binom{A}{k} x^{2k}$

$(1+x)^{B-A} = \sum_{m=0}^{B-A} \binom{B-A}{m} x^m$

Now, when we multiply these two expansions, the coefficient of $x^n$ is obtained by summing terms where $2k + m = n$. So, $m = n - 2k$. We need to sum over all valid pairs of $k$ and $m$ such that $0 \leq k \leq A$, $0 \leq m \leq B-A$, and $m = n - 2k$.

Substituting $m$: the coefficient of $x^n$ is

$\sum_{k=0}^A (-1)^k \binom{A}{k} \binom{B-A}{n-2k}

This is our sum, but expressed in a different form. For this sum to be non-zero, we need at least one term in the summation to be non-zero. A term is non-zero if and only if both binomial coefficients are non-zero. That is, we need:

1. $0 \leq k \leq A$
2. $0 \leq n-2k \leq B-A$

This implies $2k \leq n$ and $n - (B-A) \leq 2k$. Combining these, we get:

$\max(0, n - (B-A)) \leq 2k \leq \min(n, 2A)$

For our original sum to be non-zero, there must exist at least one integer $k$ that satisfies these conditions.

However, there's a more direct approach using a known combinatorial identity related to the coefficient of $x^n$ in $(1-x)^A(1+x)^B$. This coefficient is non-zero if and only if $n$ is not