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 we view our children as stupid, naughty, disturbed, or guilty of their misdeeds, they will learn to behold themselves as foolish, faulty, or shameful specimens of humanity. They will regard us as judges from whom they wish to hide, and they will interpret everything we say as further proof of their unworthiness. If we view them as innocent, or at least merely ignorant, they will gain understanding from their experiences, and they will continue to regard us as wise partners.”
    —Polly Berrien Berends (20th century)