Ken Ward's Mathematics Pages

Series Sums of Binomial Coefficients

Series Contents

Page Contents

1. Vandermonde's Convolution (Vandermonde's Identity)
1. Combinatorial Proof
2. Convolution Proof
2. Identity 2: A Positive k in  Each Lower Index
3. Identity 3: One positive k in the lower index, and one in the alternate upper index
4. Identity 4: Minus k in the top index, and plus k in the bottom one
5. Identity 5: Minus k in one upper index, and plus k in another

Vandermonde's Convolution

A convolution is a wriggling and writhing together, which nicely describes how two polynomials, when multiplied or divided, have the terms of one, interacting with the terms of the other.

Vandermonde's Convolution is:
[1.1]
Where r and s are any real numbers, and k, m and n are integers.

k, m and n must be integers because we have not defined the Binomial Coefficients with non-integer lower indexes. Therefore, 1.1 couldn't be true for other kinds of numbers.

Just looking at it (1.1), we can note that (m+k) and (n-k) must be greater than zero. So k>=-m, and k<=n.

When k=-m, then the second factor lower index becomes (n+m), and produces a polynomial in s of degree at most (m+n).

When k=n, then the first factor becomes a polynomial in r of degree at most (m+n).

So, by the polynomial argument, if we can show that both sides of this equation (1.1) are equal on (r+s+1) occasions, then we have proved they are equal for all real r and s. As we do not know what r+s is, (but we know it is finite), we need to find an infinity of examples where both sides of the equation are equal.

We can take m=0, because m is a constant, and if 1.1 is true for all integers m, it will be true for m=0.

The equation to prove is therefore:
[1.2]

Combinatorial Proof

Suppose we have to select n objects from r round objects and s square ones. The numbers r and s are nonnegative integers.

If we do this, by choosing
0 round objects and n square ones
1 round object and n-1 square ones
2 round objects and n-2 square ones
...
n round objects and 0 square ones.

(Of course some or all of these sets may be empty).

We can choose these in the following way:
[2.1]

Which is the left hand side of 1.2 expanded;
[1.2, repeated]

Because the relationship is true for an infinity of nonnegative integers, by the polynomial argument, it is true for all real r and s.

Convolution Proof

We first note:
[3.1]
Taking r, s and n as nonnegative integers, and using the Binomial Theorem for nonnegative integers. Or using another method, such as the Method of Unknown Coefficients, and taking r and n as any real numbers. n is the general n-th term.

And:
[3.2]

If we convolve these by multiplying them, we shall obtain the equivalent of the following:
[3.3]

The sum of the terms making the n-th term of the product (and also of 3.3) is:
[3.4]
k is a number between 0 and n inclusive.

The left-hand side is the n-th term of Equation 3.3, and the right-hand side is the sum of all the partial results for the n-th term of the product of 3.1 and 3.2.

So we get an xⁿ, by multiplying the first term of 3.1 by the n-th term of 3.2, and similarly multiplying all the products that make up the n-th term.

The right-hand side of 3.4 is the expansion of the left-hand side of:
[1.2, repeated]

We finally argue that the two polynomials on each side of the equation are equal, because they are at most degree n and they are equal in an infinite number of places (for all the nonnegative integers). The equation is therefore true for all real r and s.

This formula can give us a way to a closed form of a sum of the products of two Binomial Coefficients, even when the k's are variously placed in the upper and lower indices.

Identity 2: A Positive k in  Each Lower Index

The following identity has a positive k in each the lower index. The l and s values are nonnegative integers. [4.1]

A simply application of symmetry (which works only with nonnegative integers) gives:
[4.2]

One of the k's is now negative, so we can apply Vandermonde, which immediately shows the equality.

The original assumption that l, m, n are nonnegative integers has not been changed.

Identity 3: One positive k in the lower index, and one in the alternate upper index

Identity 5.1 has a k in the lower index of one factor and another k in the upper index of the other:
[5.1]

We assume that l, m, and s are nonnegative integers, so we can use symmetry.

As we require a positive k in one factor and a negative in the other (both in the lower index), we need to move the top k to the bottom. First we use symmetry:
[5.2]

We now have a k in both lower indices.

Now upper negation on the second factor to eliminate the k in the upper index:
[5.3]

Applying symmetry to the first term, and noting: the index becomes (-1)^(s+2k-n)=(-1)^s(-1)^2k(-1)^-n, the factor  (-1)^2k is ((-1)²)^k=(1)^k=1, we have:
[5.4]

Which is a sum of products with constant terms in the upper indices and a plus and a minus k in the bottom (making the sum of the lower indices a constant too), and so we can apply Vandermonde's Convolution, and add up the top indices and the bottom indices, to get:
[5.5]

We can negate the upper index, simplify the powers of (-1), then apply symmetry:
[5.6]

We note that:
[5.7]

The right-hand side is what we sought to prove.

The assumption of nonnegative integers remains.

Equivalent Indices Note

On indices of a different kind... we note the following, which shows that (-1)^l-m=(-1)^l+m:
[5.8]

Identity 4: Minus k in the top index, and plus k in the bottom one

The relationship below has a minus k in the top index of the first factor, and a positive k in the lower index of the second factor. [6.1]

Assuming m, n, s are nonnegative integers, we can apply symmetry:
[6.2]
Also for symmetry, we have assumed k<=l

To remove the k in the upper index of the first factor, we use upper negation on the first factor:
[6.3]

(The minus k in the powers cancels out). We can now apply Vandermonde's Convolution:
[6.4]

Which gives us the right-hand side after noting (-1)^l-m=(-1)^l+m.

Our assumptions on nonnegative integers remain unchanged.

Identity 5: Minus k in one upper index, and plus k in another

The following identity has k's in the upper indices.
[7.1]

The first thing to do, in order to apply Vandermonde's Convolution, is to bring the k's down into the lower indices, using symmetry, and then we can use upper negation to remove the k's from the upper indices.

As usual, we assume nonnegative integers so we can use symmetry.
[7.2]

Now, we remove the upper indices using upper negation:
[7.3]

We can now apply Vandermonde's Convolution:
[7.4]

Applying upper summation again, we get the required result.
[7.5]
































Ken Ward's Mathematics Pages

---

---

Faster Arithmetic - by Ken Ward