Combinatorial identity: $\sum\limits_{k=0}^{i\land j}\binom ik(-1)^k\binom{i+j-k}i=1$ Let $i,j\in\mathbb Z_{\ge0}$ be nonnegative integers. How can we prove
$$\sum_{k=0}^{i\land j}\binom ik(-1)^k\binom{i+j-k}i=1?$$
(Here, $i\land j=\min(i,j)=\min\{i,j\}=\min(\{i,j\})$ is the minimum of $i$ and $j.$ This problem comes from my study of stationary distributions of birth-death chains.)
By the identity
$$\binom ik\binom{i+j-k}i=\frac{(i+j-k)!}{k!(i-k)!(j-k)!}=\binom{i+j-k}{k,i-k,j-k},$$
we have
$$\sum_{k=0}^{i\land j}\binom ik(-1)^k\binom{i+j-k}i=\sum_{k=0}^{i\land j}(-1)^k\binom{i+j-k}{k,i-k,j-k}.$$
I was thinking of using the trinomial theorem, but I don't see how -- the form of the sum seems a bit different.
 A: Suppose that you want to count the $i$-element subsets of $[i]=\{1,2,\ldots,i\}$. Of course there’s only one of them, but we can also count them by the following roundabout procedure. We first expand the set from which we’re drawing the $i$-element subset to $[i+j]=\{1,\ldots,i+j\}$. Now for each $\ell\in[i]$ let $A_\ell$ be the family of $i$-element subsets of $[i+j]$ that do not contain $\ell$; $\bigcup_{\ell=1}^iA_\ell$ is the family of $i$-elements subsets of $[i+j]$ that are not subsets of $[i]$. By the inclusion-exclusion principle we have
$$\begin{align*}
\left|\bigcup_{\ell=1}^iA_\ell\right|&=\sum_{\varnothing\ne I\subseteq[i]}(-1)^{|I|+1}\left|\bigcap_{\ell\in I}A_\ell\right|\\
&=\sum_{k=1}^i\binom{i}k(-1)^{k+1}\binom{i+j-k}i\;,
\end{align*}$$
since each non-empty $I\subseteq[i]$ has cardinality in $[i]$, for each $k\in[i]$ there are $\binom{i}k$ subsets of $[i]$ of cardinality $k$, and if $|I|=k$, 
$$\left|\bigcap_{\ell\in I}A_\ell\right|=\binom{i+j-k}i\;.$$
There are $\binom{i+j}i$ $i$-element subsets of $[i+j]$ altogether, so after we throw out the ones not contained in $[i]$, we have left
$$\begin{align*}
\binom{i+j}i&-\sum_{k=1}^i\binom{i}k(-1)^{k+1}\binom{i+j-k}i\\
&=\binom{i+j}i+\sum_{k=1}^i\binom{i}k(-1)^k\binom{i+j-k}i\\
&=\sum_{k\ge 0}\binom{i}k(-1)^k\binom{i+j-k}i\;,
\end{align*}$$
and we already know that this is $1$. 
Note that there is no need to specify an upper limit on the summation: $\binom{i}k=0$ when $k>i$, and $\binom{i+j-k}i=0$ when $k>j$, so all terms with $k>i\land j$ are $0$ anyway.
A: We seek to verify that
$$\sum_{k=0}^{\min(p,q)} {p\choose k} (-1)^k {p+q-k\choose p} =1.$$
Re-write as
$$\sum_{k=0}^{\min(p,q)} {p\choose k} (-1)^k {p+q-k\choose q-k}
\\ = [z^q] (1+z)^{p+q}
\sum_{k=0}^{\min(p,q)} {p\choose k} (-1)^k \frac{z^k}{(1+z)^k}.$$
Now when $k\gt q$ the coefficient extractor makes for a zero
contribution. With $p\ge 0$ we have $p^{\underline{k}} = 0$ when $k\gt
p.$ The upper limit is enforced and we may continue with
$$[z^q] (1+z)^{p+q}
\sum_{k\ge 0} {p\choose k} (-1)^k \frac{z^k}{(1+z)^k}
\\ = [z^q] (1+z)^{p+q} \left(1-\frac{z}{1+z}\right)^p
= [z^q] (1+z)^{p+q} (1+z)^{-p}
= [z^q] (1+z)^q = 1.$$
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
&\bbox[10px,#ffd]{\sum_{k = 0}^{\min\braces{i,j}}{i \choose k}\pars{-1}^{k}{i + j - k \choose i}} =
\sum_{k = 0}^{\min\braces{i,j}}{i \choose k}\pars{-1}^{k}
{i + j - k \choose j - k}
\\[5mm] = &\
\sum_{k = 0}^{\min\braces{i,j}}{i \choose k}\pars{-1}^{k}
{-i - 1 \choose j - k}\pars{-1}^{j - k} =
\pars{-1}^{j}\sum_{k = 0}^{\min\braces{i,j}}{i \choose k}
\bracks{z^{j - k}}\pars{1 + z}^{-i - 1}
\\[5mm] = &\
\pars{-1}^{j}\bracks{z^{j}}\pars{1 + z}^{-i - 1}
\sum_{k = 0}^{\min\braces{i,j}}{i \choose k}z^{k}
\\[5mm] = &\
\pars{-1}^{j}\bracks{z^{j}}\pars{1 + z}^{-i - 1}
\\[2mm] &\ \times
\braces{\bracks{i \leq j}\sum_{k = 0}^{i}{i \choose k}z^{k} +
\bracks{i > j}\bracks{\sum_{k = 0}^{i}
{i \choose k}z^{k} - \sum_{k = j + 1}^{i}{i \choose k}z^{k}}}
\\[5mm] = &\
\pars{-1}^{j}\
\underbrace{\bracks{z^{j}}\pars{1 + z}^{-i - 1}
\overbrace{\sum_{k = 0}^{i}{i \choose k}z^{k}}^{\ds{\pars{1 + z}^{i}}}}_{\ds{\pars{-1}^{j}}}\ -\
\underbrace{\bracks{i > j}\pars{-1}^{j}\color{red}{\bracks{z^{j}}z^{j + 1}}
\pars{1 + z}^{-i - 1}\sum_{k = 0}^{i - j + 1}{i \choose k}z^{k}}
_{\ds{\begin{array}{c}{\Large = 0} \\ \mbox{See the}\ \color{red}{red}\ \mbox{detail} \end{array}}}
\\[5mm] = \bbox[10px,#ffd,border:1px groove navy]{\large 1} \\ &\
\end{align}
