CombinatorialIdentity Challenging

Problem - 4292

Let $p$, $q$, and $n$ be three positive integers, show that $$\sum_{k=0}^n\binom{p+k}{p}\binom{q+n-k}{q} = \binom{p+q+n+1}{p+q+1}$$


Utilizing the conclusion of # 4284 can yield $$\frac{1}{(1-x)^{p+1}}=\sum_{k=0}^{\infty}\binom{p+k}{p}x^k\quad\text{and}\quad\frac{1}{(1-x)^{q+1}}=\sum_{k=0}^{\infty}\binom{q+k}{q}x^k$$

It follows that $$\begin{align*} \frac{1}{(1-x)^{p+1}}\cdot\frac{1}{(1-x)^{q+1}}=\ &\left(\displaystyle\sum_{k=0}^{\infty}\binom{p+k}{p}x^k\right)\left(\displaystyle\sum_{k=0}^{\infty}\binom{q+k}{q}x^k\right) \\ \\=\ &\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\binom{p+k}{p}\binom{q+n-k}{q}\right)x^n \end{align*}$$

Meanwhile, we also have $$\frac{1}{(1-x)^{p+1}}\cdot\frac{1}{(1-x)^{q+1}}=\frac{1}{(1-x)^{p+q+2}}=\sum_{n=0}^{\infty}\binom{p+q+n+1}{p+q+1}x^n$$

Comparing the right sides of the above two relations leads to the desired result immediately.

report an error