# Show that $\sum_{j=m-1}^{n-1}(-1)^{j-m+1}\binom{j}{m-1}\binom{n}{j+1}=1$ for $n\ge m$

I tried to verify that $$\sum_{j=m-1}^{n-1}(-1)^{j-m+1}\binom{j}{m-1}\binom{n}{j+1}=1$$ for $n\ge m$.

I believe I can use induction on $n$ and Pascal’s formula to justify this; but I wanted to see if there was a way to prove this formula without using induction.

#### Solutions Collecting From Web of "Show that $\sum_{j=m-1}^{n-1}(-1)^{j-m+1}\binom{j}{m-1}\binom{n}{j+1}=1$ for $n\ge m$"

You can use generating functions:
$$(-1)^{j-m+1}\binom{j}{m-1}$$
is the coefficient of $t^j$ in $t^{m-1}/(1+t)^m$ and
$$\binom{n}{j+1}$$
is the coefficient of $t^{n-j-1}$ in $(1+t)^n$. Your sum is the
coefficient of $t^{n-1}$ in the product of $t^{m-1}/(1+t)^m$
and $(1+t)^n$.

Here is a slightly different variation based upon generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write e.g.
\begin{align*}
[z^k](1+z)^n=\binom{n}{k}
\end{align*}

We obtain for $1\leq m\leq n$
\begin{align*}
\color{blue}{\sum_{j=m-1}^{n-1}}&\color{blue}{(-1)^{j-m+1}\binom{j}{m-1}\binom{n}{j+1}}\\
&=\sum_{j=0}^{n-m}(-1)^{j}\binom{j+m-1}{j}\binom{n}{j+m}\tag{1}\\
&=\sum_{j=0}^{n-m}\binom{-m}{j}\binom{n}{j+m}\tag{2}\\
&=\sum_{j=0}^\infty[z^j](1+z)^{-m}[t^{j+m}](1+t)^n\tag{3}\\
&=[t^m](1+t)^n\sum_{j=0}^\infty t^{-j}[z^j](1+z)^{-m}\tag{4}\\
&=[t^m](1+t)^n\left(1+\frac{1}{t}\right)^{-m}\tag{5}\\
&=[t^0](1+t)^{n-m}\tag{6}\\
&\color{blue}{=1}
\end{align*}

Comment:

• In (1) we shift the index to start with $j=0$ and apply $\binom{p}{q}=\binom{p}{p-q}$.

• In (2) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (3) we apply the coefficient of operator twice and set the upper limit of the series to $\infty$ without changing anything since we are adding zeros only.

• In (4) we use the linearity of the coefficient of operator and apply the rule $[z^{p+q}]A(z)=[z^p]z^{-q}A(z)$.

• In (5) we apply the substitution rule of the coefficient of operator with $z:=1/t$
\begin{align*}
A(t)=\sum_{j=0}^\infty a_j t^j=\sum_{j=0}^\infty t^j [z^j]A(z)
\end{align*}

• In (6) we do some simplifications and are ready to select the coefficient of $[t^0]$.

Using Induction

The Cancellation Lemma from this answer says that
$$\sum_{j=m-1}^{n-1}(-1)^{j-m+1}\binom{j+1}{m}\binom{n}{j+1}=[n=m]\tag{1}$$
Then Pascal’s Rule implies that
\begin{align} a_{n,m} &=\sum_{j=m-1}^{n-1}(-1)^{j-m+1}\binom{j}{m-1}\binom{n}{j+1}\\ &=\sum_{j=m-1}^{n-1}(-1)^{j-m+1}\left[\binom{j+1}{m}-\binom{j}{m}\right]\binom{n}{j+1}\\[9pt] &=[n=m]+a_{n,m+1}\tag{2} \end{align}
and the Binomial Theorem says that
\begin{align} a_{n,1} &=\sum_{j=0}^{n-1}(-1)^j\binom{j}{0}\binom{n}{j+1}\\ &=\sum_{j=1}^n(-1)^{j-1}\binom{n}{j}\\ &=1-\sum_{j=0}^n(-1)^j\binom{n}{j}\\[6pt] &=1-0^n\\[15pt] &=[n\ge1]\tag{3} \end{align}
$(2)$ and $(3)$ combine to give
$$\sum_{j=m-1}^{n-1}(-1)^{j-m+1}\binom{j}{m-1}\binom{n}{j+1}=[n\ge m]\tag{4}$$
where $[\cdots]$ are Iverson Brackets.

Using Generating Functions
\begin{align} &\sum_{n=0}^\infty\sum_{j=m-1}^{n-1}(-1)^{j-m+1}\binom{j}{m-1}\binom{n}{j+1}x^n\\ &=\sum_{j=m-1}^\infty\sum_{n=j+1}^\infty(-1)^{j-m+1}\binom{j}{m-1}\binom{n}{n-j-1}x^n\tag{5a}\\ &=\sum_{j=m-1}^\infty\sum_{n=j+1}^\infty(-1)^{j-m+1}\binom{j}{m-1}(-1)^{n-j-1}\binom{-j-2}{n-j-1}x^n\tag{5b}\\ &=\sum_{j=m-1}^\infty\sum_{n=0}^\infty(-1)^{n+j-m+1}\binom{j}{m-1}\binom{-j-2}{n}x^{n+j+1}\tag{5c}\\ &=\sum_{j=m-1}^\infty(-1)^{j-m+1}\binom{j}{m-1}\frac{x^{j+1}}{(1-x)^{j+2}}\tag{5d}\\ &=\sum_{j=m-1}^\infty\binom{-m}{j-m+1}\frac{x^{j+1}}{(1-x)^{j+2}}\tag{5e}\\ &=\sum_{j=0}^\infty\binom{-m}{j}\frac{x^{j+m}}{(1-x)^{j+m+1}}\tag{5f}\\ &=\frac{x^m}{(1-x)^{m+1}}\left(\frac1{1-x}\right)^{-m}\tag{5g}\\[6pt] &=\frac{x^m}{1-x}\tag{5h} \end{align}
Explanation:
$\text{(5a)}$: switch order of summation and use symmetry of Pascal’s Triangle
$\text{(5b)}$: equate with negative binomial coefficient
$\text{(5c)}$: substitute $n\mapsto n+j+1$
$\text{(5d)}$: apply the Binomial Theorem
$\text{(5e)}$: equate with negative binomial coefficient
$\text{(5f)}$: substitute $j\mapsto j+m-1$
$\text{(5g)}$: apply the Binomial Theorem
$\text{(5h)}$: algebra

Equation $(5)$ yields $(4)$ as well.

Here is an alternate proof where the goal was novelty. Start with

$$\sum_{j=m-1}^{n-1} (-1)^{j-m+1} {j\choose m-1} {n\choose j+1} \\ = n \sum_{j=m-1}^{n-1} \frac{(-1)^{j-m+1}}{j+1} {j\choose m-1} {n-1\choose j}.$$

Observe that

$${j\choose m-1} {n-1\choose j} = \frac{(n-1)!}{(n-1-j)! \times (m-1)! (j-m+1)!} \\ = {n-1\choose m-1} {n-m\choose n-1-j}.$$

We get for the sum

$$n {n-1\choose m-1} \sum_{j=m-1}^{n-1} \frac{(-1)^{j-m+1}}{j+1} {n-m\choose n-1-j} \\ = n {n-1\choose m-1} \sum_{j=0}^{n-m} \frac{(-1)^{j}}{j+m} {n-m\choose n-m-j} \\ = n {n-1\choose m-1} \sum_{j=0}^{n-m} \frac{(-1)^{j}}{j+m} {n-m\choose j}.$$

Introduce

$$f(z) = (n-m)! (-1)^{n-m} \frac{1}{z+m} \prod_{q=0}^{n-m} \frac{1}{z-q}.$$

Then we have for $0\le j\le n-m$

$$\mathrm{Res}_{z=j} f(z) = (n-m)! (-1)^{n-m} \frac{1}{j+m} \prod_{q=0}^{j-1} \frac{1}{j-q} \prod_{q=j+1}^{n-m} \frac{1}{j-q} \\ = (n-m)! (-1)^{n-m} \frac{1}{j+m} \frac{1}{j!} \frac{(-1)^{n-m-j}}{(n-m-j)!} = \frac{(-1)^j}{j+m} {n-m\choose j}.$$

Now since $\lim_{R \to\infty} 2\pi R / R^{1+n-m+1} = \lim_{R \to\infty} 2\pi / R^{n-m+1} = 0$ we have
$\mathrm{Res}_{z=\infty} f(z) = 0$ and hence

$$\sum_{j=0}^{n-m} \frac{(-1)^{j}}{j+m} {n-m\choose j} = – \mathrm{Res}_{z=-m} f(z) \\ = – (n-m)! (-1)^{n-m} \prod_{q=0}^{n-m} \frac{1}{-m-q} = (n-m)! \prod_{q=0}^{n-m} \frac{1}{m+q} \\ = (n-m)! \frac{(m-1)!}{n!} = \frac{1}{n} {n-1\choose m-1}^{-1}.$$

It follows that our closed form is

$$n {n-1\choose m-1} \times \frac{1}{n} {n-1\choose m-1}^{-1} = 1.$$