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)\).
