0
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.