In this question, the definition of \(\displaystyle\binom pq\)
is taken to be
\[
\binom pq =
\begin{cases}
\dfrac{p!}{q!(p-q)!} & \text{ if } p\ge q\ge0 \,,\\[4mm]
0 & \text{ otherwise } .
\end{cases}
\]
Write down the coefficient of \(x^n\) in the binomial expansion
for \((1-x)^{-N}\), where \(N\) is a positive integer, and write
down the expansion
using the \(\Sigma\) summation notation.
By considering
$
(1-x)^{-1} (1-x)^{-N}
\,
,$
where \(N\) is a positive integer, show that
\[
\sum_{j=0}^n \binom { N+j -1}{j} = \binom{N+n}{n}\,.
\]
Show that,
for any positive integers \(m\), \(n\) and \(r\) with \(r\le m+n\),
\[
\binom{m+n} r = \sum _{j=0}^r \binom m j \binom n {r-j}
\,.
\]
Show that, for any positive integers \(m\) and \(N\),
\[
\sum_{j=0}^n(-1)^{j} \binom {N+m} {n-j} \binom {m+j-1}{j } =
\displaystyle \binom N n
.
\]
Solution:
\(\frac{(-N)(-N-1)\cdots(-N-n+1)}{n!} = \binom{N+n-1}{n}\), so
\[ (1-x)^{-N} = \sum_{n=0}^{\infty} \binom{N+n-1}{n} x^n\]
\begin{align*}
&& (1-x)^{-N-1} &= (1-x)^{-1}(1-x)^{-N} \\
&&&= (1 + x + x^2 + \cdots)\left ( \sum_{n=0}^{\infty} \binom{N+n-1}{n} x^n\right)\\
[x^{n}]: && \binom{N+1+n-1}{n} &= \sum_{j=0}^n \underbrace{1}_{x^{n-j} \text{ from 1st bracket}}\cdot\underbrace{\binom{N+j-1}{j}}_{x^j\text{ from second bracket}} \\
\Rightarrow && \binom{N+n}{n} &= \sum_{j=0}^n \binom{N+j-1}{j}
\end{align*}
Consider \((1+x)^{m+n} = (1+x)^m(1+x)^n\) and consider the coefficient of \(x^r\) from each side. On the left hand side this is clearly \(\binom{m+n}{r}\) on the right hand side we can take \(x^j\) from \((1+x)^m\) and \(x^{n-j}\) from \((1+x)^n\) and \(j\) can take any value from \(0\) to \(r\), ie
\[ \binom{m+n} r = \sum _{j=0}^r \binom m j \binom n {r-j} \]