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

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.

• that very nice. Thank prof Scott ! May 29, 2020 at 2:53
• You probably mean something other than $\bigcup_{\ell=i+1}^{i+j}A_{\ell};$ you've only defined $A_\ell$ for $1\le\ell\le i,$ not for $i+1\le\ell\le i+j.$ May 29, 2020 at 13:45
• @xFioraMstr18: Thanks! Yes, I started out on a slightly different tack and apparently missed that one when I changed everything. May 29, 2020 at 17:18

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

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