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.
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
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]
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]
the relationship is true for an infinity of nonnegative integers, by
the polynomial argument, it is true for all real r and s.
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.
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.
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 xn, 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]
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.
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.
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.
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)2)k=(1)k=1, we have: [5.4]
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
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]
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]