A quick post about the sum of products of binomial coefficients

Consider both binomial theorem and multinomial theorem. Start from (1+x)^mn:

Which gives rise to:

The coefficient of x^p would satisfy the three conditions:

Hence, the coefficient of x^p from (1+x)^(m+n) could be expressed as:

In this case we define m = 2. Therefore,

Recall what we defined C() as:

Quod erat demonstrandum.

＊

Here are some examples:

＊

Though we used polynomial of x to demonstrate this proof and yield our required result (the coefficient of x^p), what the value of x really is doesn't matter, and hence we don't define it. The same conception can be in generating function, where we would suppose 0<x<1 so that we could simplify the whole expression with infinitife series.

＊

LaTeX 語法：

\sum_{i=0}^m\binom{n}{i}\binom{n}{m-i}=\binom{2n}{m}

\begin{align*}
(1+x)^{m\times n}&=\left [ (1+x)^n \right ]^m=\left [ \sum_{i=0}^n\binom{n}{i}x^i \right ]^m \\
 & = \sum_{i=0}^{m\times n}\binom{m\times n}{i}x^i
\end{align*}

\begin{align*}

\left [ \sum_{i=0}^n\binom{n}{i}x^i \right ]^m &= \sum_{\sum k_i=m} \frac{m!}{k_0!k_1!\cdots k_n!}\left [ \binom{n}{0} x^0 \right ]^{k_0}\left [ \binom{n}{1} x^1 \right ]^{k_1}\cdots \left [ \binom{n}{n} x^n \right ]^{k_n} \\

 & = \sum_{\sum k_i=m}x^{\Sigma\: ik_i}\:m!\prod_{i=0}^n\frac{\binom{n}{i}^{k_i}}{k_i!} \\

 & \overset{de\!f}{=}\sum_{\sum k_i=m}x^{\Sigma\: ik_i}\;\mathrm{C}(\text{condition})

\end{align*}

\begin{align*}
\text{Coef}\left (x^p \right )&=\text{C}\left ( k_0=k_p=1 \right ) \\
&+ \text{C} \left ( k_1 = k_{p-1} = 1 \right ) \\
&+ \cdots \\
&+ \text{C}\left ( k_{\left \lfloor \frac{p}{2} \right \rfloor} = k_{\left \lceil \frac{p}{2} \right \rceil} =1\right ) \text{when p is odd} \\
& \text{or}\; \text{C}\left ( k_{\frac{p}{2}}=2 \right ) \text{when p is even}
\end{align*}

\begin{align*}
\text{Coef}\left (x^p \right ) &= 2\binom{n}{0}\binom{n}{p}+ 2\binom{n}{p-1}\binom{n}{1} + \cdots\\
&= \binom{n}{p}\binom{n}{0}+\binom{n}{p-1}\binom{n}{1}+\cdots+\binom{n}{1}\binom{n}{p-1}+\binom{n}{0}\binom{n}{p} \\
&= \sum_{i=0}^p \binom{n}{i}\binom{n}{p-i}\qquad \blacksquare
\end{align*}