# Combinatorial identity involving binomial coefficients.

In order to conclude a proof (see last equality in B. Poonen's article), I need to establish the following identity:

$$\forall (\ell,n)\in\mathbb{N}^2,\ell\leqslant n,\sum_{m=\ell}^n{n\choose m}{m\choose \ell}(-1)^{m-\ell}=\left\{\begin{array}{ll}1&\textrm{, if }\ell=n\\0&\textrm{, else}\end{array}\right..$$

I have no clue whether or not this identity is true, although I checked it on the first values of $(\ell,n)$, $(\ell,n)\in\{1,\cdots,15\}^2$.

Any hints will be greatly appreciated!

First note that

$$\binom{n}m\binom{m}\ell=\binom{n}\ell\binom{n-\ell}{m-\ell}\;,$$

so

\begin{align*} \sum_{m=\ell}^n\binom{n}m\binom{m}\ell(-1)^{m-\ell}&=\sum_{m=\ell}^n\binom{n}\ell\binom{n-\ell}{m-\ell}(-1)^{m-\ell}\\ &=\binom{n}\ell\sum_{m=\ell}^n(-1)^{m-\ell}\binom{n-\ell}{m-\ell}\\ &=\binom{n}\ell\sum_{k=0}^{n-\ell}(-1)^k\binom{n-\ell}k\;. \end{align*}

Now

$$\sum_{k=0}^{n-\ell}(-1)^k\binom{n-\ell}k=\begin{cases} 1,&\text{if }n=\ell\\ 0,&\text{otherwise}\;, \end{cases}$$

and $\dbinom{n}n=1$, so indeed

$$\sum_{m=\ell}^n\binom{n}m\binom{m}\ell(-1)^{m-\ell}=\begin{cases} 1,&\text{if }n=\ell\\ 0,&\text{otherwise}\;. \end{cases}$$

@Brian M. Scott

It is an immediate consequence of the product of the upper triangular Pascal matrix $P_n$ and its inverse. See https://en.wikipedia.org/wiki/Pascal_matrix

Recall that the generic coefficient of $A=P_n$ is $a_{ij}=\begin{cases}\binom{i}{j}&\text{if } \ i \geq j\\0&\text{in the other cases}\end{cases}$

Recall that the generic coefficient of $B=P_n^{-1}$ is $b_{ij}=\begin{cases}(-1)^{i-j}\binom{i}{j}&\text{if } \ i \geq j\\0&\text{in the other cases}\end{cases}$

I will show it on the example of $n=5$, with an immediate generalization:

$$\begin{bmatrix}1 & 2 & 3 & 4 & 5\\ 0 & 1 & 3 & 6 & 10\\ 0 & 0 & 1 & 4 & 10\\ 0 & 0 & 0 & 1 & 5\\ 0 & 0 & 0 & 0 & 1\end{bmatrix} \begin{bmatrix}1 & -2 & 3 & -4 & 5\\ 0 & 1 & -3 & 6 & -10\\ 0 & 0 & 1 & -4 & 10\\ 0 & 0 & 0 & 1 & -5\\ 0 & 0 & 0 & 0 & 1\end{bmatrix}= \begin{bmatrix}1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\end{bmatrix}$$

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \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{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#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} &\color{#f00}{\sum_{m = \ell}^{n}{n \choose m}{m \choose \ell} \pars{-1}^{m - \ell}} = \pars{-1}^{\ell}\sum_{m = 0}^{\infty}\pars{-1}^{m}{n \choose \ell} {n - \ell \choose m - \ell} \\[3mm] = &\ \pars{-1}^{\ell}{n \choose \ell}\sum_{m = 0}^{\infty}\pars{-1}^{m} {n - \ell \choose n - m} = \pars{-1}^{\ell}{n \choose \ell}\sum_{m = 0}^{\infty}\pars{-1}^{m}\ \overbrace{% \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{n - \ell} \over z^{n - m + 1}} \,{\dd z \over 2\pi\ic}}^{\ds{=\ {n - \ell \choose n - m}}} \\[3mm] = & \pars{-1}^{\ell}{n \choose \ell} \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{n - \ell} \over z^{n + 1}} \sum_{m = 0}^{\infty}\pars{-z}^{m}\,{\dd z \over 2\pi\ic} = \pars{-1}^{\ell}{n \choose \ell}\ \overbrace{% \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{n - \ell - 1} \over z^{n + 1}} \,{\dd z \over 2\pi\ic}}^{\ds{=\ {n - \ell - 1 \choose n}}} \\[3mm] = &\ \pars{-1}^{\ell}{n \choose \ell}{n - \ell - 1 \choose n} = \pars{-1}^{\ell}{n \choose \ell}\ \underbrace{% {-n + \ell + 1 + n - 1 \choose n}\pars{-1}^{n}} _{\ds{=\ {n - \ell - 1 \choose n}}} \\[3mm] = &\ \pars{-1}^{\ell + n}{n \choose \ell}{\ell \choose n} = \color{#f00}{\left\lbrace\begin{array}{l} \ds{1\quad\mbox{if}\quad\ell = n} \\ \ds{0}\quad\mbox{otherwise} \end{array}\right.} \end{align}