Exercise 1.4.3 (Vandermonde's identity)

Question

\begin{enumerate}
\item[(a)] By comparing the coefficient of $z^k$ in the polynomial identity
\begin{align*}
\sum_{k=0}^{m+n} \binom{m+n}{k} z^k &= (1+z)^{m+n} = (1+z)^m (1+z)^n\
&= \left( \sum_{k=0}^m \binom{m}{k} z^kight)\left( \sum_{k=0}^n \binom{n}{k} z^kight)
\end{align*}
show that
$$\sum_{i=0}^k \binom{m}{i} \binom{n}{k-i} = \binom{m+n}{k}.$$

\item[(b)] Let $\mathscr{U}$ and $\mathscr{V}$ be disjoint sets containing $m$ and $n$ elements, respectively, and put $\mathscr{S} = \mathscr{U} \cup \mathscr{V}$. Show that the number of subsets $\mathscr{A}$ of $\mathscr{S}$ that contain $k$ elements and that also have the property that $\mathscr{A} \cap \mathscr{U}$ contains $i$ elements is $\binom{m}{i} \binom{n}{k-i}$. Interpret this identity combinatorially.

\item[(c)] Show that for $n\geq 0$,
$$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}.$$
\end{enumerate}

Richard Ganaye · Accepted Answer

\begin{proof}
\begin{enumerate}
\item[(a)]
 All is said in the sentence. Let $z$ be a variable (indeterminate). We calculate $(1+z)^{m+n}$ in two ways.

First
\begin{align}
(1+z)^{m+n} &= \sum_{k=0}^{m+n} \binom{m+n}{k} z^k.
\end{align}

Next 
\begin{align*}
(1+z)^{m+n} &= (1+z)^m (1+z)^n\
&= \left( \sum_{i=0}^m \binom{m}{i} z^iight)\left( \sum_{j=0}^n \binom{n}{j} z^jight)\
&=\sum_{k=0}^{m+n} \left(  \sum_{i = 0}^{k}  \binom{m}{i}  \binom{n}{k-i}ight) z^k, \
\end{align*}
using the definition of multiplication of two polynomials, which  gives $$\left(\sum_{i=0}^m a_i z^iight)\left( \sum_{j=0}^n b_j z^j ight)= \sum_{k=0}^{m+n} \left( \sum_{i=0}^k a_i b_{k-i}ight) z^k.$$

So
\begin{align}
(1+z)^{m+n} &= \sum_{k=0}^{m+n} \left(  \sum_{i = 0}^{k}  \binom{m}{i}  \binom{n}{k-i}ight) z^k.
\end{align}
The comparison of the two polynomials identities (1) and (2) gives
$$\sum_{i=0}^k \binom{m}{i} \binom{n}{k-i} = \binom{m+n}{k}.$$
(Vandermonde's identity.)

\bigskip 
Note: $\binom{m}{i} = 0$ if $i >m$, and $\binom{n}{k-i} = 0$ if $k-i >n$. Therefore we can keep only the indices $i$ such that $i\geq 0, i \geq k-n$, and $i \leq m, i \leq k$, so
$$\sum_{i=\max(0, k-n)}^{\min(m,k)} \binom{m}{i} \binom{n}{k-i} = \binom{m+n}{k}.$$

\item[(b)] Here $\mathscr{S} = \mathscr{U} \cup \mathscr{V}$ and $\varnothing = \mathscr{U} \cap \mathscr{V}$, where $|\mathscr{U}| = m, |\mathscr{V}| = n$, so $|\mathscr{S}| = m+n$.

Now consider the set $M_i$ of subsets $\mathscr{A}$ of $\mathscr{S}$ containing $k$ elements, such that $\mathscr{A} \cup \mathscr{U}$ contains $i$ elements, where $0 \leq i \leq k$.

$$ M_i = \{\mathscr{A} \in \mathscr{P}(S):  |\mathscr{A} \cup \mathscr{U}| = i\}.$$
(Imagine a box filled with $m$ white balls and $n$ black balls, and consider the draws of $k$ balls simultaneously which contains $i$ white balls, and so $k-i$ black balls).

If $\mathscr{A} \in M_i$, then
$$\mathscr{A} = (\mathscr{A} \cap \mathscr{U} ) \cup (\mathscr{A} \cap \mathscr{V}), \qquad  \varnothing = (\mathscr{A} \cap \mathscr{U} ) \cap (\mathscr{A} \cap \mathscr{V} ).$$
Therefore $|\mathscr{A} \cap \mathscr{V}| = k-i$.

Now we compute the cardinality of $M_i$. Recall that we write $\mathscr{P}_k(E)$ for the set of subsets of $E$ containing $k$ elements.

Consider the map
$$
\varphi
\left\{
\begin{array}{ccl}
M_i & 	o & \mathscr{P}_i(\mathscr{U}) 	imes \mathscr{P}_{k-i}(\mathscr{V}) \
\mathscr{A} &\mapsto & (\mathscr{A} \cap \mathscr{U}, \mathscr{A} \cap \mathscr{V})
\end{array}
ight.
$$
Since $|\mathscr{A} \cap \mathscr{U}| = i$ and $|\mathscr{A} \cap \mathscr{V}| = k-i$ for every $\mathscr{A} \in M_i$, the definition of $\varphi$ makes sense. Moreover $\varphi$ is a bijection: let 
$$
\psi
\left\{
\begin{array}{ccl}
 \mathscr{P}_i(\mathscr{U}) 	imes \mathscr{P}_{k-i}(\mathscr{V})  & 	o &M_i\
(R,S) & \mapsto & R \cup S.
\end{array}
ight.
$$
(Let  $(R,S) \in \mathscr{P}_i(\mathscr{U}) 	imes \mathscr{P}_{k-i}(\mathscr{V}) $. Then $R \cap S = \varnothing$ and $|R| = i,|S| = k-i$, thus $|R \cup S| = i + (k-i) = k$, and $(R \cup S) \cap \mathscr{U} = R$, where $|R| = i$, so $R \cup S \in M_i$.)

Then for every $\mathscr{A} \in M_i$, $(\psi \circ \varphi)(\mathscr{A})=  (\mathscr{A} \cap \mathscr{U} ) \cup (\mathscr{A} \cap \mathscr{V}) = \mathscr{A}$, so $\psi \circ \varphi = 1_{M_i}$, and for every $(R,S) \in  \mathscr{P}_i(\mathscr{U}) 	imes \mathscr{P}_{k-i}(\mathscr{V}) $, 
\begin{align*}
(\varphi \circ \psi)(R,S) &= \varphi(R \cup S)\
&=((R\cup S) \cap\mathscr{U}, (R\cup S) \cap \mathscr{V})\
&=(R \cap \mathscr{U}) \cup (S \cap \mathscr{U}),(R \cap \mathscr{V}) \cup (S \cap \mathscr{V}))\
&=(R,S),
\end{align*}
because $R \subset \mathscr{U}, S \subset \mathscr{V}$ and $\mathscr{U} \cap \mathscr{V} = \varnothing.$

Since $\psi \circ \varphi = 1_{M_i}$ and $\varphi \circ \psi = 1_{ \mathscr{P}_i(\mathscr{U}) 	imes \mathscr{P}_{k-i}(\mathscr{V})}$, $\varphi$ is bijective.

Therefore
$$|M_i| = | \mathscr{P}_i(\mathscr{U}) 	imes \mathscr{P}_{k-i}(\mathscr{V})| = | \mathscr{P}_i(\mathscr{U})| 	imes |\mathscr{P}_{k-i}(\mathscr{V})| = \binom{m}{i} \binom{n}{k-i}.$$
(In less formal terms, we choose $i$ white balls between $m$ white balls, and $k-i$ black balls between $n$ black balls, which gives $\binom{m}{i} \binom{n}{k-i}$ choices.)

This gives a new proof of the Vandermonde's identity.

Note that $\mathscr{S} = \bigcup_{i=0}^k M_i$, since every element $ \mathscr{A} \in \mathscr{S}$ satisfies $|\mathscr{A} \cap \mathscr{U}| = i$ for some $i \in [\![0,k]\!]$.

This union is disjoint because $0 \leq  i < i' \leq k \Rightarrow M_i \cap M_{i'} = \varnothing$ ($|\mathscr{A} \cap \mathscr{U}| = i$ and $|\mathscr{A} \cap \mathscr{U}| = i'$ are incompatible if $i
e i'$).

Therefore
$$\binom{m+n}{k} = |\mathscr{S}| = \sum_{i=0}^k |M_i| = \sum_{i=0}^k \binom{m}{i} \binom{n}{k-i}.$$
This is the Vandermonde's identity.

\item[(c)] If we take $m=n$ and $k=n$ in the Vandermonde's identity, we obtain
\begin{align*}
\binom{2n}{n} &= \sum_{i=0}^n \binom{n}{i} \binom{n}{n-i} \
&=\sum_{i=0}^n \binom{n}{i}^2,
\end{align*}
using the symmetry (1.10) $\binom{n}{n-i} = \binom{n}{i}$.
\end{enumerate}
\end{proof}

Exercise 1.4.3 (Vandermonde's identity)

Answers

Comments

Exercise 1.4.3 (Vandermonde's identity)

Answers

Comments

Add answer