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)

    “When children feel good about themselves, it’s like a snowball rolling downhill. They are continually able to recognize and integrate new proof of their value as they grow and mature.”
    —Stephanie Martson (20th century)