The Multi-Approach Method Intermediate

Lecture Notes

In proving the Vandermonde Identity, we used two different approaches to count the same thing. Here is another example: $$k{n\choose k}=n{n-1\choose k-1}$$

This idenity can be proved by applying the basic definition of ${n\choose k}$. Alternatively, it can also be explained by using two different approaches to solve the same counting problem. Please see the second solution in the example $1$ (# 2681).

Using two different approaches to count the same thing is not the only way to use this method. There are several other ways. One of them is to compare the coefficients of the same term in a polynomial identity. For example, we can prove the Vandermone identity by comparing the coefficient of the term $x^r$ at the left and right sides of the following identity (the second solution in example $2$:# 4274): $$(1+x)^m(1+x)^n = (1+x)^{m+n}$$


Examples

(2681)

Show that $$\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$$

(4274)

(Vandermonde's Identity) Show that $$\displaystyle\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}$$

        click the problem # to see the solution.

Assignment >>>
Comments

Note: determining the coefficient of a term, e.g. $x^r$, in the expansion of $(1+x)^m(1+x)^n$ is a basic but important skill to have.

Vandermonde Identity
table of contents
Generating Function

report error