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