I was playing around with some polynomials involving binomial coefficients, and inadvertently proved the following two identities:

(1) For all $p, q \in \mathbb{N}$ and $i \in \left[ 0, \min\{p, q\} \right]$: $$ \begin{pmatrix}p \\ i\end{pmatrix} = \sum_{j=0}^i (-1)^j \begin{pmatrix}q \\ j\end{pmatrix} \begin{pmatrix}p + q - j \\ i - j\end{pmatrix} \text{.} $$

(2) For all $q \in \mathbb{N}_{\ge 1}$ and $i \in [0, q]$: $$ \frac{q - i}{q} = \sum_{j=0}^i (-1)^j \begin{pmatrix}i \\ j\end{pmatrix} \begin{pmatrix}2q - 1 - j \\ i - j\end{pmatrix} \begin{pmatrix}q - j \\ i - j\end{pmatrix}^{-1} \text{.} $$

Can either of these identities be proven in any trivial way (e.g., by reduction to known identities)?


The first one is just inclusion-exclusion in the following way:
Take the set $[p+q]=\{1,\cdots ,p+q\},$ so you want to take $i$ elements from those such that they all belong to $[p].$ By definition you just restrict yourself to the set $[p]$ and hence there are $\binom{p}{i}$, but on the other hand it is the same as this $$|T\setminus \bigcup _{j=1}^q A_{p+j}|,$$ where $T$ is take all possible subsets of size $i$ from $[p+q]$ which can be done in $\binom{p+q}{i}$ and $A_r = \{S\subset [p+q]:|S|=i \wedge r\in S\}$ (so we are taking out all sets that contain elements on $[p+q]\setminus [p]$.)

By inclusion-exclusion then $$|T\setminus \bigcup _{j=1}^q A_{p+j}|=|T|-\sum _{j=1}^q(-1)^{j-1}\sum _{X\in \binom{[p+q]\setminus [p]}{j}}|\bigcap _{y\in X} A_{y}|,$$ as seeing before, $|T|=\binom{p+q}{i},$ and $|A_r|=\binom{p+q-1}{i-1}$ and if you take $r_1,r_2\in [p+q]\setminus [p],$ $|A_{r_1}\cap A_{r_2}|=\binom{p+q-2}{i-2}$ because you have already chosen $2$, hence the intersections are homogeneous and then $$|T|-\sum _{j=1}^q(-1)^{j-1}\sum _{X\in \binom{[p+q]\setminus [p]}{j}}|\bigcap _{y\in X} A_{y}|=\binom{p+q}{i}-\sum _{j=1}^q(-1)^{j-1}\sum _{X\in \binom{[p+q]\setminus [p]}{j}}\binom{p+q-j}{i-j}=\binom{p+q}{i}-\sum _{j=1}^q(-1)^{j-1}\binom{q}{j}\binom{p+q-j}{i-j},$$ what is you identity.
The second one seems more challenging(but it suggests a probabilistic approach.)

Added: The second is a particular case of the first one.

Notice that $\frac{\binom{i}{j}}{\binom{q-j}{i-j}}=\frac{(q-i)!i!}{j!(q-j)!}=\frac{\binom{q}{j}}{\binom{q}{i}},$ so on the LHS you get $$\binom{q-1}{i},$$ and then take $p=q-1$ in your first identity and the result follows.


For what it's worth in verifying that

$${p\choose r} = \sum_{j=0}^r (-1)^j {q\choose j} {p+q-j\choose r-j}$$

we may introduce

$${p+q-j\choose r-j} = {p+q-j\choose p+q-r} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r-j+1}} \frac{1}{(1-z)^{p+q+1-r}} \; dz$$

which vanishes when $j\gt r$ so we may extend $j$ to infinity and get for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r+1}} \frac{1}{(1-z)^{p+q+1-r}} \sum_{j\ge 0} (-1)^j {q\choose j} z^j \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r+1}} \frac{1}{(1-z)^{p+q+1-r}} (1-z)^q \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r+1}} \frac{1}{(1-z)^{p+1-r}} \; dz$$

This evaluates by inspection to

$${r+p-r\choose p-r} = {p\choose p-r} = {p\choose r}.$$


$\newcommand{\bbx}[1]{\,\bbox[8px,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}$

$\ds{\sum_{j = 0}^{i}\pars{-1}^{\,j}{q \choose j}{p + q - j \choose i - j} = {p \choose i}.\qquad p, q \in \mathbb{N}\,;\quad i \in \bracks{0,\min\braces{p,q}}}$.

From the above conditions it's clear, because $\ds{j \leq i}$, that $\ds{p + q - j \geq 0}$. Then, $\ds{{p + q - j \choose i - j}_{j\ >\ i} = 0}$ such that $\color{#f00}{the\ above\ sum\ can\ be\ extended}$ to all numbers $\ds{\in \mathbb{N}}$: \begin{align} &\sum_{j = 0}^{i}\pars{-1}^{\,j}{q \choose j}{p + q - j \choose i - j} = \sum_{j = 0}^{\color{#f00}{\infty}}\pars{-1}^{\,j}{q \choose j}\ \overbrace{{-p - q + i- 1 \choose i - j}\pars{-1}^{i - j}}^{\ds{p + q - j \choose i - j}} \\[5mm] = &\ \pars{-1}^{i}\sum_{j = 0}^{\infty}{q \choose j} \braces{\vphantom{\huge A}\bracks{z^{i - j}}\pars{1 + z}^{-p - q + i - 1}} = \pars{-1}^{i}\bracks{z^{i}}\braces{\vphantom{\huge A}% \pars{1 + z}^{-p - q + i - 1}\ \overbrace{\sum_{j = 0}^{\infty}{q \choose j}z^{j}}^{\ds{\pars{1 + z}^{q}}}} \\[5mm] = &\ \pars{-1}^{i}\bracks{z^{i}}\pars{1 + z}^{-p + i - 1} = \pars{-1}^{i}{-p + i - 1 \choose i} \\[5mm] = &\ \pars{-1}^{i}\ \underbrace{{-\bracks{-p + i - 1} + i - 1 \choose i}\pars{-1}^{i}} _{\ds{-p + i - 1 \choose i}}\ =\ \bbx{\ds{p \choose i}} \end{align}

  • $\begingroup$ The accepted answer shows that the second identity is just a special case of the first (and so your current solution seems to be doing more work than necessary). But I like how your first solution shows this directly (this is the closest to how I found them). $\endgroup$ – Aaron Voelker Mar 25 '17 at 20:32
  • $\begingroup$ @AaronVoelker Thanks. I erased part 2. $\endgroup$ – Felix Marin Mar 26 '17 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.