Probability, Random Variables, and Random Processes: Theory and Signal Processing Applications

E.7 VANDERMONDE'S IDENTITY

Theorem E.1 (Vandermonde). For :

(E.46)

Proof. Consider the following form of the binomial theorem:

(E.47)

which is a polynomial in x of degree m + n. Expressing the right-hand side above as a product and applying the binomial theorem twice gives

(E.48)

Collecting terms with like-exponents of x, it is straightforward to rearrange this expression as follows:

(E.49)

which gives

(E.50)

Note that binomial coefficients where the bottom number exceeds the top number are defined to be zero. Both sides have sums over k that provide the exponents of x in a polynomial of degree m + n. Equating coefficients of xk on both sides gives the result in (E.46), which completes the proof.

Example E.1. This proof is verified by the following simple case. Consider the product (x + 1)2(x + 1) in (E.48) where m = 2 and n = 1. The last part of the proof in (E.49) is the following ...