0 like 0 dislike
37 views
Prove the Vandermonde identity.

For integers $N, M, n \geq 0$, the following identity holds:
$\sum_{k=0}^n\left(\begin{array}{l} N \\ k \end{array}\right)\left(\begin{array}{c} M \\ n-k \end{array}\right)=\left(\begin{array}{c} N+M \\ n \end{array}\right)$
| 37 views

0 like 0 dislike
Proof: Sums of the form
$\sum_{k=0}^n a_k b_{n-k}$
are reminiscent of polynomial multiplication: If two polynomials $A(x)=\sum_{k=0}^N a_k x^k$ and $B(x)=\sum_{l=0}^M b_l x^l$ are given, then one obtains for the product of the two
$A(x) \cdot B(x)=\sum_{k=0}^N \sum_{l=0}^M a_k b_l x^{k+l} .$
The coefficient of $x^n$ is obtained from those terms for which $k+l=n$, or equivalently $l=n-k$. It follows that the coefficient of $x^n$ equals
$\sum_{k=0}^n a_k b_{n-k}$
where we set $a_k=0$ if the degree $N$ of the polynomial $A$ is less than $k$ (and likewise $b_l=0$ if $l>M$ ). The same argument is also used later in Section 4.3.

In the present case the problem can be solved by applying the binomial theorem to the polynomial $(1+x)^{N+M}$, which is also the product of the two polynomials $(1+x)^N$ and $(1+x)^M$
$(1+x)^{N+M}=(1+x)^N \cdot(1+x)^M=\left(\sum_{k=0}^N\left(\begin{array}{c} N \\ k \end{array}\right) x^k\right)\left(\sum_{l=0}^M\left(\begin{array}{c} M \\ l \end{array}\right) x^l\right)$

$=\sum_{k=0}^N \sum_{l=0}^M\left(\begin{array}{c} N \\ k \end{array}\right)\left(\begin{array}{c} M \\ l \end{array}\right) x^{k+l}=\sum_{n=0}^{N+M} \sum_{k=0}^n\left(\begin{array}{c} N \\ k \end{array}\right)\left(\begin{array}{c} M \\ n-k \end{array}\right) x^n .$
Now we obtain the desired identity upon comparing coefficients with
$(1+x)^{N+M}=\sum_{n=0}^{N+M}\left(\begin{array}{c} N+M \\ n \end{array}\right) x^n .$
Once again, it is possible to prove the identity by means of a simple counting argument: consider a set of $N+M$ elements, and divide it into two parts with $N$ and $M$ elements respectively. If one wants to select $n$ elements, one can do so by first choosing $k$ elements from the first part $(k \leq n)$ and the remaining $n-k$ elements from the second part. For each $k$, there are precisely $\left(\begin{array}{c}N \\ k\end{array}\right)\left(\begin{array}{c}M \\ n-k\end{array}\right)$ possibilities. Summing over all $k$, we obtain the above expression for $\left(\begin{array}{c}N+M \\ n\end{array}\right)$.
by Platinum (163,814 points)

0 like 0 dislike
1 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
0 like 0 dislike