From $(1+z)^p(1+z)^q=(1+z)^{p+q}$ show that $\sum\limits_{n=0}^r\binom{p}{n}\binom{q}{r-n}=\binom{p+q}{r}$ without using the Cauchy product

Question

I'm stuck on what was an easy exercise at first sight. It's exercise 18, PSet 15.3, Kreyszig "Advanced Engineering Mathematics" 10th ed. It asks to prove that given $(1+z)^p(1+z)^q=(1+z)^{p+q}$ then $\sum\limits_{n=0}^r\binom{p}{n}\binom{q}{r-n}=\binom{p+q}{r}$.

Taking for granted that $(1+z)^p=\sum\limits_{k=0}^p\binom{p}{k} z^k$ and from

$$\sum\limits_{n=0}^p\binom{p}{n} z^n \sum\limits_{m=0}^q\binom{q}{m} z^m=\sum\limits_{r=0}^{p+q}\binom{p+q}{r} z^r$$

I should be able to manipulate the indices to get $\sum\limits_{r=0}^{p+q}\sum\limits_{n=0}^{r}\binom{p}{n} \binom{q}{r-n}z^r$ but I can't. My attempt was noticing that there is a constraint for which $n+m=r$ and $m,n>0$:

$$ \sum\limits_{n=0}^p\binom{p}{n} z^n \sum\limits_{m=0}^q\binom{q}{m} z^m=\sum\limits_{n=0}^p\sum\limits_{m=0}^q\binom{p}{n}\binom{q}{m} z^{n+m}=\sum\limits_{n=0}^p\sum\limits_{r=n}^{q+n}\binom{p}{n}\binom{q}{r-n} z^r=\\ =\sum\limits_{r=n}^{q+n}\sum\limits_{n=0}^p\binom{p}{n}\binom{q}{r-n} z^r$$

This is the closest I can get to $\sum\limits_{r=0}^{p+q}\sum\limits_{n=0}^{r}\binom{p}{n} \binom{q}{r-n}z^r$. Can anyone help me?

Thanks, Luca

Answer 1

The transformations are fine up to \begin{align*} \sum_{n=0}^p\sum_{r=n}^{q+n}\binom{p}{n}\binom{q}{r-n}z^r\tag{1} \end{align*}

But note the representation \begin{align*} \sum_{r=n}^{q+n}\sum_{n=0}^p\binom{p}{n}\binom{q}{r-n}z^r \end{align*} is not valid, since the index $r$ in the outer sum starts with $r=n$, but $n$ is not defined. The scope of the inner index $n$ does not extend to the outer sum.

Nevertheless we can derive the following continuing with (1) \begin{align*} \sum_{n=0}^p\sum_{r=n}^{q+n}\binom{p}{n}\binom{q}{r-n}z^r &=\sum_{n=0}^{p+q}\sum_{r=n}^{p+q}\binom{p}{n}\binom{q}{r-n}z^r\tag{2}\\ &=\sum_{0\leq n\leq r\leq p+q}\binom{p}{n}\binom{q}{r-n}z^r\tag{3}\\ &=\sum_{r=0}^{p+q}\color{blue}{\sum_{n=0}^{r}\binom{p}{n}\binom{q}{r-n}}z^r\tag{4}\\ \end{align*} which is the representation we are looking for. Comparison of coefficients with \begin{align*} (1+z)^{p+q}=\sum_{r=0}^{p+q}\color{blue}{\binom{p+q}{r}}z^r \end{align*} shows the wanted result (without using the Cauchy product formula).

Comment:

• In (2) we set the upper limit of the sums to $p+q$ by noting that $\binom{n}{k}=0$ if $n,k\in\mathbb{N}$ and $k>n$.

• In (3) we just use another presentation of the index range to better see the situation.

• In (4) we exchange the sums by respecting the range of the indices indicated in (3).

Answer 2

HINT.-What you need is just the well known product of polynomials

$$(a_0x^p+a_1x^{p-1}+\cdots+a_{p-1}x+a_p)\cdot(b_0x^q+b_1x^{q-1}+\cdots+b_{q-1}x+b_q)=\sum\limits_{n=0}^{p+q}c_nx^n.... (*)$$ where $c_n=\sum\limits_{k=0}^na_kb_{n-k}$ applied to the multiplication of two polynomials $$\binom p0 z^p+\binom p1 z^{p-1}+\cdots+\binom {p}{p-1}z+\binom pp$$ $$\binom q0 z^q+\binom q1 z^{q-1}+\cdots+\binom {q}{q-1}z+\binom qq$$ The formule you want is just both $(*)$ with the obvious $(1+z)^p\cdot(1+z)^q=(1+z)^{p+q}$.

Another way is to apply induction.

Answer 3

You don't have to take for granted that $\;(1+z)^p=\displaystyle\sum_{k=0}^p\binom{p}{k} z^k$ : it's the definition of binomial coefficients.

Just wonder how one can obtain a term of degree $r$ from $\;\displaystyle\sum _{n=0}^p\binom{p}{n} z^n\cdot \sum_{m=0}^q\binom{q}{m} z^m$ : due tio distributivity, just take a term $\;\displaystyle\binom{p}{n} z^n$ from the first factor and a term $\;\displaystyle\binom{p}{m} z^m$ so that $n+m=r$, in all possible ways, and add them. In other words: $$\binom{p+q}rz^r=\sum_{\begin{matrix}n+m=r\\[-0.76ex]0\le n\le p\\[-0.5ex]0\le m\le q\end{matrix}}\binom{p}{n} z^n\cdot\binom{q}{m} z^m. $$ If you observe that from $n+m=r$, you deduce that $m=r-n$, you obtain readily $$\binom{p+q}r=\sum_{n=0}^r\binom{p}{n} \binom{q}{n-r}, $$being understood that if it happens that $n>p$ or $n-r>q$, then $\dbinom pn=0\;$ or $\dbinom q{n-r}=0$ respectively.