Vandermonde's Identity - Algebraic Proof

Algebraic Proof

In general, the product of two polynomials with degrees m and n, respectively, is given by

\biggl(\sum_{i=0}^m a_ix^i\biggr) \biggl(\sum_{j=0}^n b_jx^j\biggr) = \sum_{r=0}^{m+n}\biggl(\sum_{k=0}^r a_k b_{r-k}\biggr) x^r,

where we use the convention that ai = 0 for all integers i > m and bj = 0 for all integers j > n. By the binomial theorem,

Using the binomial theorem also for the exponents m and n, and then the above formula for the product of polynomials, we obtain

\begin{align} \sum_{r=0}^{m+n} {m+n \choose r}x^r &= (1+x)^{m+n}\\ &= (1+x)^m (1+x)^n \\ &= \biggl(\sum_{i=0}^m {m\choose i}x^i\biggr) \biggl(\sum_{j=0}^n {n\choose j}x^j\biggr)\\ &=\sum_{r=0}^{m+n}\biggl(\sum_{k=0}^r {m\choose k} {n\choose r-k}\biggr) x^r, \end{align}

where the above convention for the coefficients of the polynomials agrees with the definition of the binomial coefficients, because both give zero for all i > m and j > n, respectively.

By comparing coefficients of xr, Vandermonde's identity follows for all integers r with 0 ≤ r ≤ m + n. For larger integers r, both sides of Vandermonde's identity are zero due to the definition of binomial coefficients.

Read more about this topic:  Vandermonde's Identity

Famous quotes containing the words algebraic and/or proof:

    “I have no scheme about it,—no designs on men at all; and, if I had, my mode would be to tempt them with the fruit, and not with the manure. To what end do I lead a simple life at all, pray? That I may teach others to simplify their lives?—and so all our lives be simplified merely, like an algebraic formula? Or not, rather, that I may make use of the ground I have cleared, to live more worthily and profitably?”
    —Henry David Thoreau (1817–1862)

    “If any proof were needed of the progress of the cause for which I have worked, it is here tonight. The presence on the stage of these college women, and in the audience of all those college girls who will some day be the nation’s greatest strength, will tell their own story to the world.”
    —Susan B. Anthony (1820–1906)