Some curious binomial coefficient identities

Question

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)?

Answer 1

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.

Answer 2

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

Answer 3

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