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:
is the coefficient of $t^j$ in $t^{m-1}/(1+t)^m$ and
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.

We obtain for $1\leq m\leq n$
&=[t^m](1+t)^n\sum_{j=0}^\infty t^{-j}[z^j](1+z)^{-m}\tag{4}\\


  • 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$
    A(t)=\sum_{j=0}^\infty a_j t^j=\sum_{j=0}^\infty t^j [z^j]A(z)

  • 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
Then Pascal’s Rule implies that
and the Binomial Theorem says that
$(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
$\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}.$$


$$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

\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.$$