Question

Use generating functions to prove Vandermonde's identity:

\(C(m + n,r) = \sum\limits_{k = 0}^r C (m,r - k)C(n,k)\), whenever \(m\) , \(n\) , and \(r\) are nonnegative integers with \(r\) not exceeding either \(m\) or \(n\).

Short answer

The resultant answer is \(C(m + n,r) = \sum\limits_{k = 0}^r C (m,r - k)C(n,k)\).

Step-by-step solution

Given data

The given data is \(m,n,r\) are nonnegative and \(r\) does not exceed \(m\) or \(n\).

Concept of Extended binomial theorem

Generating function for the sequence \({a_0},{a_1}, \ldots ,{a_k}, \ldots \) of real numbers is the infinite series: \(G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}\)

Extended binomial theorem: \({(1 + x)^u} = \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{l}}u\\k\end{array}} \right)} {x^k}\).

Use the binomial theorem and simplify the expression

Use the binomial theorem:

\(\begin{array}{l}{(1 + x)^m}{(1 + x)^n} = \left( {\sum\limits_{r = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}m\\r\end{array}} \right)} {x^r}} \right)\left( {\sum\limits_{r = 0}^{ + \infty } {\left( {\begin{array}{*{20}{l}}n\\r\end{array}} \right)} {x^r}} \right)\\{(1 + x)^m}{(1 + x)^n} = \left( {\sum\limits_{r = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right)} {x^r}} \right)\left( {\sum\limits_{r = 0}^{ + \infty } {\left( {\begin{array}{*{20}{l}}m\\r\end{array}} \right)} {x^r}} \right)\\{(1 + x)^m}{(1 + x)^n} = \sum\limits_{r = 0}^{ + \infty } {\left( {\sum\limits_{k = 0}^r {\left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right)} \left( {\begin{array}{*{20}{c}}n\\{r - k}\end{array}} \right)} \right)} {x^k}\end{array}\)

Further, solve the above expression,

\(\begin{array}{l}{(1 + x)^m}{(1 + x)^n} = \sum\limits_{r = 0}^{ + \infty } {\left( {\sum\limits_{k = 0}^r C (n,k)C(m,r - k)} \right)} {x^k}\\{(1 + x)^m}{(1 + x)^n} = \sum\limits_{r = 0}^{ + \infty } {\left( {\sum\limits_{k = 0}^r C (m,r - k)C(n,k)} \right)} {x^k}\end{array}\)

Since \({(1 + x)^{m + n}} = {(1 + x)^m}{(1 + x)^n}\), gives

\(\sum\limits_{r = 0}^{ + \infty } C (m + n,r){x^r} = \sum\limits_{k = 0}^{ + \infty } {\left( {\sum\limits_{k = 0}^r C (m,r - k)C(n,k)} \right)} {x^k}\)

The corresponding coefficients then have to be equal: \(C(m + n,r) = \sum\limits_{k = 0}^r C (m,r - k)C(n,k)\).