# Combinatorial Identity with Connection Coefficients and Falling Factorial $\langle i x\rangle_n$

Let $j, k ,n$ be nonnegative integers such that $0 \leq j, k \leq n \leq k +j$. Pick integer $m$ such that $0 \leq m \leq k + j - n$.

Let $\langle x \rangle_m$ denote the falling factorial $x(x-1)\ldots (x-m+1)$.

I've stumbled across the need to prove the following equality:

$$\sum_{i=0}^n \frac{\binom{k}{i}\binom{j}{i}}{\binom{n}{i}}(-1)^i\langle ix\rangle_m = \left\{ \begin{matrix} \frac{k! j!}{n!} (-x)^m ~~~~~~~~\text{when }m = k+j - n\\ 0 ~~~~~~~~~~~~~~~~~\text{when }m < k + j - n \end{matrix} \right.$$ An equivalent formulation is: $$\sum_{i=0}^n \frac{(-1)^i\binom{k}{i}\binom{j}{i} \binom{i x}{m}}{\binom{n}{i}}= \left\{ \begin{matrix} \frac{k! j!}{n!m!} (-x)^m ~~~~~~~~\text{when }m = k+j - n\\ 0 ~~~~~~~~~~~~~~~~~\text{when }m < k + j - n \end{matrix} \right.$$ Any references to potentially related material would be greatly appreciated.

${\scriptsize \textbf{Edited to fix sign}}$

• There's lots of material on generalized Stirling numbers of the first and second kind that might contain the identity. – Tom Copeland Dec 2 '16 at 1:59
• At least some signs are missing. I get $-3/10 x$ for $j=3$, $k=3$, $n=5$ and $m=1$. – darij grinberg Dec 2 '16 at 6:28
• Probably it's worthwhile to replace $\dbinom{ix}{m}$ by a general $m$-th degree polynomial $c_m i^m + c_{m-1} i^{m-1} + \cdots + c_0$ in $i$ (regarding all other variables as constant). Then, it's probably only the $c_m i^m$ part that matters, and we can replace it by $\dbinom{i}{m}$. – darij grinberg Dec 2 '16 at 6:33
• Ah yes, this boils down to a finite difference argument. – darij grinberg Dec 2 '16 at 6:35
• @darijgrinberg can you elaborate? None of the finite difference arguments I have seen involve two binomial coefficients $\binom{k}{i}\binom{j}{i}$ – Nick R Dec 2 '16 at 7:01

It is very probable that what is written below is the simplification of Darij's argument. I use the notation $x^{\underline{n}}=x(x-1)\dots(x-n+1)$ [as in Knuth's books] for the falling factorial, and $[t^n] f(t)$ for the coefficient of $t^n$ in the polynomial $f$.

For a polynomial $f(t)$ of degree at most $j$ we have $$\sum_{i=0}^j (-1)^{j-i}\frac{f(i)}{i!(j-i)!}=[t^j]f(t),$$ this follows from the Lagrange interpolation of $f$ in the points $\{0,1,\dots,j\}$. Apply this to the polynomial $f(t)=(tx)^{\underline m}(n-t)^{\underline {n-k}}$. In RHS we have 0 if $m<k+j-n$ and $(-1)^{n-k}x^m$ if $m=k+j-n$. In LHS we get $$\sum_{i=0}^{\min(j,k)} (-1)^{j-i}\frac{(n-i)!(ti)^{\underline m}}{(k-i)!i!(j-i)!}=(-1)^j\frac{n!}{k!j!}\sum_{i=0}^{\min(j,k)} (-1)^{i}\frac{\binom{k}i\binom{j}i}{\binom{n}i}(ti)^{\underline m}$$ and we are done.

This is correct. Let me prove a more general fact:

Theorem 1. Let $i$, $j$ and $n$ be three nonnegative integers such that $i\leq n$ and $j\leq n$. Let $P\in\mathbb{Q}\left[ X\right]$ be a polynomial such that $\deg P\leq i+j-n$. For every $m\in\mathbb{Z}$, let $\left[ X^{m}\right] P$ denote the coefficient of $X^{m}$ in $P$. Then, $\sum\limits_{u=0}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}\dbinom{j} {u}}{\dbinom{n}{u}}P\left( u\right) = \left(-1\right)^{i+j-n} \dfrac{i!j!}{n!}\left[ X^{i+j-n}\right] P$.

From this fact, the following follows:

Corollary 2. Let $i$, $j$ and $n$ be three nonnegative integers such that $i\leq n$ and $j\leq n$. Let $v\in\mathbb{R}$ and $m\in\left\{ 0,1,\ldots ,i+j-n\right\}$. Then, $\sum\limits_{u=0}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}\dbinom{j}{u}}{\dbinom{n}{u}}\dbinom{uv}{m}= \begin{cases} \left(-1\right)^{i+j-n} \dfrac{i!j!}{n!m!}v^{m}, & \text{if }m=i+j-n;\\ 0, & \text{if }m<i+j-n \end{cases}$.

Corollary 2 (applied to $k$ and $x$ instead of $i$ and $v$) yields your question.

Proof of Corollary 2 using Theorem 1. Define a polynomial $P\in \mathbb{Q}\left[ X\right]$ by $P=\dbinom{vX}{m}$. Then, $\deg P\leq m\leq i+j-n$ and $\left[ X^{m}\right] P=\dfrac{v^{m}}{m!}$ (because if we expand the product in the numerator of $P=\dbinom{vX}{m}=\dfrac{\left( vX\right) \left( vX-1\right) \cdots\left( vX-m+1\right) }{m!}$, then the only term of degree $m$ in $X$ will be $\left( vX\right) \left( vX\right) \cdots\left( vX\right)$, thus leading to the coefficient $\dfrac{v^{m}} {m!}$).

Since $m\in\left\{ 0,1,\ldots,i+j-n\right\}$, we are in one of the following two cases:

Case 1: We have $m=i+j-n$.

Case 2: We have $m<i+j-n$.

Let us first consider Case 1. In this case, we have $m=i+j-n$. Hence, $i+j-n=m$, so that $\left[ X^{i+j-n}\right] P=\left[ X^{m}\right] P=\dfrac{v^{m}}{m!}$. But Theorem 1 yields

$\sum\limits_{u=0}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}\dbinom{j} {u}}{\dbinom{n}{u}}P\left( u\right) = \left(-1\right)^{i+j-n} \dfrac{i!j!}{n!}\underbrace{\left[ X^{i+j-n}\right] P}_{=\dfrac{v^{m}}{m!}}= \left(-1\right)^{i+j-n} \dfrac{i!j!}{n!m!}v^{m}$

$= \begin{cases} \left(-1\right)^{i+j-n} \dfrac{i!j!}{n!m!}v^{m}, & \text{if }m=i+j-n;\\ 0, & \text{if }m<i+j-n \end{cases}$ (since $m=i+j-n$).

Since $P\left( u\right) =\dbinom{vu}{m}=\dbinom{uv}{m}$, this rewrites as

$\sum\limits_{u=0}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}\dbinom{j} {u}}{\dbinom{n}{u}}\dbinom{uv}{m}= \begin{cases} \left(-1\right)^{i+j-n} \dfrac{i!j!}{n!m!}v^{m}, & \text{if }m=i+j-n;\\ 0, & \text{if }m<i+j-n \end{cases}$.

Hence, Corollary 2 is proven in Case 1.

Let us now consider Case 2. In this case, we have $m<i+j-n$. Thus, $\deg P\leq m<i+j-n$, so that $\left[ X^{i+j-n}\right] P=0$. But Theorem 1 yields

$\sum\limits_{u=0}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}\dbinom{j} {u}}{\dbinom{n}{u}}P\left( u\right) = \left(-1\right)^{i+j-n} \dfrac{i!j!}{n!}\underbrace{\left[ X^{i+j-n}\right] P}_{=0}=0$

$= \begin{cases} \left(-1\right)^{i+j-n} \dfrac{i!j!}{n!m!}v^{m}, & \text{if }m=i+j-n;\\ 0, & \text{if }m<i+j-n \end{cases}$ (since $m<i+j-n$).

Since $P\left( u\right) =\dbinom{vu}{m}=\dbinom{uv}{m}$, this rewrites as

$\sum_{u=0}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}\dbinom{j}{u} }{\dbinom{n}{u}}\dbinom{uv}{m}= \begin{cases} \left(-1\right)^{i+j-n} \dfrac{i!j!}{n!m!}v^{m}, & \text{if }m=i+j-n;\\ 0, & \text{if }m<i+j-n \end{cases}$.

Hence, Corollary 2 is proven in Case 2.

We now have proven Corollary 2 in both cases (using Theorem 1). It remains to prove Theorem 1.

In the following, $\mathbb{N}$ means the set $\left\{ 0,1,2,\ldots\right\}$. We will use the following facts:

Lemma 3. If $m\in\mathbb{Z}$, $a\in\mathbb{N}$ and $i\in\mathbb{N}$ are such that $i\geq a$, then $\dbinom{m}{i}\dbinom{i}{a}=\dbinom{m}{a}\dbinom{m-a}{i-a}$.

Lemma 3 is the so-called trinomial revision identity, and proving it is a simple exercise in formal manipulations. Notice that the right definition of binomial coefficients to use here is $\dbinom{m}{p}=\dfrac{m\left( m-1\right) \cdots\left( m-p+1\right) }{p!}$, since this works for every $m\in\mathbb{Z}$ (not only for $m\geq p$).

Lemma 4. Let $N\in\mathbb{Z}$. Let $\mathcal{P}_{N}$ be the set of all polynomials $P\in\mathbb{Q}\left[ X\right]$ of degree $\leq N$. Then, $\mathcal{P}_{N}$ is a subspace of the $\mathbb{Q}$-vector space $\mathbb{Q}\left[ X\right]$, and has basis $\left( \dbinom{X}{0} ,\dbinom{X}{1},\ldots,\dbinom{X}{N}\right)$.

Lemma 4 is well-known.

Lemma 5. Let $q\in\mathbb{N}$ and $r\in\mathbb{Z}$ and $s\in\left\{ 0,1,\ldots,q\right\}$. Then, $\sum\limits_{u=0}^{q}\left( -1\right) ^{u}\dbinom{q}{u}\dbinom{r-u}{s}= \begin{cases} 1, & \text{if }s=q;\\ 0, & \text{if }s<q \end{cases}$.

Lemma 5 is again a fairly basic fact. You might know it in this very form, or recognize it as a particular case of the fact that the $q$-th finite difference of a polynomial of degree $\leq q$ is an easily-described constant. (Here, the polynomial is $\dbinom{r-X}{s}$, whose degree is $s\leq q$.) Probably, inclusion-exclusion yields a combinatorial proof for $r$ high enough. In the interest of getting some sleep this week, I will leave the proof to the reader.

Here is a corollary of Lemma 5 that will be useful to us:

Lemma 6. Let $q\in\mathbb{N}$ and $Q\in\mathbb{N}$ and $r\in\mathbb{Z}$ and $s\in\left\{ 0,1,\ldots,q\right\}$ be such that $Q\geq q$. Then, $\sum\limits_{u=0}^{Q}\left( -1\right) ^{u}\dbinom{q}{u}\dbinom{r-u}{s}= \begin{cases} 1, & \text{if }s=q;\\ 0, & \text{if }s<q \end{cases}$.

Proof of Lemma 6. In the sum $\sum\limits_{u=0}^{Q}\left( -1\right) ^{u}\dbinom{q}{u}\dbinom{r-u}{s}$, all the addends with $u>q$ are zero (because the factor $\dbinom{q}{u}$ makes them vanish). Hence, we can remove them from the sum without changing the value of the sum. We thus obtain

$\sum\limits_{u=0}^{Q}\left( -1\right) ^{u}\dbinom{q}{u}\dbinom{r-u}{s} =\sum\limits_{u=0}^{q}\left( -1\right) ^{u}\dbinom{q}{u}\dbinom{r-u}{s}= \begin{cases} 1, & \text{if }s=q;\\ 0, & \text{if }s<q \end{cases}$

(by Lemma 5).

Now, we can prove Theorem 1:

Proof of Theorem 1. The situation is symmetric with respect to $i$ and $j$. Hence, we WLOG assume that $i\geq j$ (otherwise, we can just interchange $i$ and $j$).

For every $N\in\mathbb{Z}$, define $\mathcal{P}_{N}$ as in Lemma 4. Then, $P\in\mathcal{P}_{i+j-n}$ (since $P$ is a polynomial of degree $\deg P\leq i+j-n$). But Lemma 4 (applied to $N=i+j-n$) yields that $\mathcal{P}_{i+j-n}$ is a subspace of the $\mathbb{Q}$-vector space $\mathbb{Q}\left[ X\right]$, and has basis $\left( \dbinom{X}{0},\dbinom{X}{1},\ldots,\dbinom{X} {i+j-n}\right)$. But the equality that we are trying to prove (namely, $\sum\limits_{u=0}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}\dbinom{j} {u}}{\dbinom{n}{u}}P\left( u\right) = \left(-1\right)^{i+j-n} \dfrac{i!j!}{n!}\left[ X^{i+j-n}\right] P$) is $\mathbb{Q}$-linear in $P$ (in the sense that both its sides depend $\mathbb{Q}$-linearly in $P$). Hence, we can WLOG assume that $P$ belongs to the above-mentioned basis of $\mathcal{P}_{i+j-n}$. Assume this. Thus, $P=\dbinom{X}{p}$ for some $p\in\left\{ 0,1,\ldots,i+j-n\right\}$. Consider this $p$. Hence,

$\left[ X^{i+j-n}\right] P= \begin{cases} \dfrac{1}{p!}, & \text{if }p=i+j-n;\\ 0, & \text{if }p<i+j-n \end{cases}$

$=\dfrac{1}{p!} \begin{cases} 1, & \text{if }p=i+j-n;\\ 0, & \text{if }p<i+j-n \end{cases}$.

In other words,

(0) $p!\left[ X^{i+j-n}\right] P= \begin{cases} 1, & \text{if }p=i+j-n;\\ 0, & \text{if }p<i+j-n \end{cases}$.

But $\deg P=p$ (since $P=\dbinom{X}{p}$). Hence, $p=\deg P\leq\underbrace{i} _{\leq n}+j-n\leq n+j-n=j$, so that $j\geq p$.

We have $P\left( u\right) =\dbinom{u}{p}$ for every $u\in\mathbb{Z}$ (since $P=\dbinom{X}{p}$). Hence,

$\sum\limits_{u=0}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}\dbinom{j} {u}}{\dbinom{n}{u}}\underbrace{P\left( u\right) }_{=\dbinom{u}{p}} =\sum\limits_{u=0}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}\dbinom{j} {u}}{\dbinom{n}{u}}\dbinom{u}{p}$

$=\sum\limits_{u=0}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}}{\dbinom {n}{u}}\dbinom{j}{u}\dbinom{u}{p}$

(1) $=\sum\limits_{u=p}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u} }{\dbinom{n}{u}}\dbinom{j}{u}\dbinom{u}{p}$

(here, we have removed all the addends with $u<p$, because the factor $\dbinom{u}{p}$ makes these addends vanish). Note that the interval $\left\{ p,p+1,\ldots,n\right\}$ might be empty, in which case the sum on the right hand side of (1) is empty; but this is okay (as usual, empty sums are $0$).

Fix $u\in\left\{ p,p+1,\ldots,n\right\}$. Lemma 3 (applied to $j$, $p$ and $u$ instead of $m$, $a$ and $i$) yields

(2) $\dbinom{j}{u}\dbinom{u}{p}=\dbinom{j}{p}\dbinom{j-p}{u-p}$.

Now, forget that we fixed $u$. We thus have proven (2) for each $u\in\left\{ p,p+1,\ldots,n\right\}$. Hence, (1) rewrites as

$\sum\limits_{u=0}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}\dbinom{j} {u}}{\dbinom{n}{u}}P\left( u\right)$

$=\sum\limits_{u=p}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}}{\dbinom {n}{u}}\dbinom{j}{p}\dbinom{j-p}{u-p}$

$=\dbinom{j}{p}\sum\limits_{u=p}^{n}\left( -1\right) ^{u}\dfrac{\dbinom {i}{u}}{\dbinom{n}{u}}\dbinom{j-p}{u-p}$

(3) $=\dbinom{j}{p}\sum\limits_{u=p}^{i}\left( -1\right) ^{u} \dfrac{\dbinom{i}{u}}{\dbinom{n}{u}}\dbinom{j-p}{u-p}$

(here, we have removed all the addends with $u>i$, because the factor $\dbinom{i}{u}$ makes these addends vanish).

Now, fix $u\in\left\{ p,p+1,\ldots,i\right\}$. Then, $u\leq i\leq n$. Hence, $n-u\in\mathbb{N}$ and $i-u\in\left\{ 0,1,\ldots,n-u\right\}$. Hence, the symmetry of Pascal's triangle (i.e., the fact that every $N\in\mathbb{N}$ and $M\in\left\{ 0,1,\ldots,N\right\}$ satisfy $\dbinom {N}{M}=\dbinom{N}{N-M}$) yields

$\dbinom{n-u}{i-u}=\dbinom{n-u}{\left( n-u\right) -\left( i-u\right) }=\dbinom{n-u}{n-i}$.

But Lemma 3 (applied to $n$ and $u$ instead of $m$ and $a$) yields

$\dbinom{n}{i}\dbinom{i}{u}=\dbinom{n}{u}\underbrace{\dbinom{n-u}{i-u} }_{=\dbinom{n-u}{n-i}}=\dbinom{n}{u}\dbinom{n-u}{n-i}$.

In other words,

(4) $\dfrac{\dbinom{i}{u}}{\dbinom{n}{u}}=\dfrac{\dbinom{n-u}{n-i} }{\dbinom{n}{i}}$.

(The denominators here are nonzero since $u\leq i\leq n$.)

Now, forget that we fixed $u$. We thus have proven (4) for each $u\in\left\{ p,p+1,\ldots,i\right\}$. Hence, (3) rewrites as

$\sum\limits_{u=0}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}\dbinom{j} {u}}{\dbinom{n}{u}}P\left( u\right)$

$=\dbinom{j}{p}\sum\limits_{u=p}^{i}\left( -1\right) ^{u}\dfrac{\dbinom {n-u}{n-i}}{\dbinom{n}{i}}\dbinom{j-p}{u-p}$

$=\dbinom{j}{p}\dbinom{n}{i}^{-1}\sum\limits_{u=p}^{i}\left( -1\right) ^{u}\dbinom{n-u}{n-i}\dbinom{j-p}{u-p}$

$=\dbinom{j}{p}\dbinom{n}{i}^{-1}\sum\limits_{u=0}^{i-p}\underbrace{\left( -1\right) ^{u+p}}_{=\left( -1\right) ^{p}\left( -1\right) ^{u} }\underbrace{\dbinom{n-\left( u+p\right) }{n-i}}_{=\dbinom{\left( n-p\right) -u}{n-i}}\underbrace{\dbinom{j-p}{\left( u+p\right) -p} }_{=\dbinom{j-p}{u}}$

(here, we have substituted $u+p$ for $u$ in the sum)

$=\dbinom{j}{p}\dbinom{n}{i}^{-1}\left( -1\right) ^{p}\sum\limits_{u=0} ^{i-p}\left( -1\right) ^{u}\dbinom{\left( n-p\right) -u}{n-i}\dbinom {j-p}{u}$

(5) $=\dbinom{j}{p}\dbinom{n}{i}^{-1}\left( -1\right) ^{p} \sum\limits_{u=0}^{i-p}\left( -1\right) ^{u}\dbinom{j-p}{u}\dbinom{\left( n-p\right) -u}{n-i}$.

Recall that $j\geq p$. Hence, $j-p\in\mathbb{N}$. Furthermore, $\underbrace{i} _{\geq j}-p\geq\underbrace{j}_{\geq p}-p\geq0$ and thus $i-p\in\mathbb{N}$. Finally, $n-i\in\left\{ 0,1,\ldots,j-p\right\}$ (since $n-\underbrace{i} _{\leq n}\geq n-n=0$ and $n-i\leq j-p$ (since $p\leq i+j-n$)). Hence, we can apply Lemma 6 to $q=j-p$, $Q=i-p$, $r=n-p$ and $s=n-i$. We thus obtain

$\sum\limits_{u=0}^{i-p}\left( -1\right) ^{u}\dbinom{j-p}{u}\dbinom{\left( n-p\right) -u}{n-i}= \begin{cases} 1, & \text{if }n-i=j-p;\\ 0, & \text{if }n-i<j-p \end{cases}$.

Therefore, (5) rewrites as

$\sum\limits_{u=0}^{n}\dfrac{\left( -1\right) ^{u}\dbinom{i}{u}\dbinom{j} {u}}{\dbinom{n}{u}}P\left( u\right)$

$=\underbrace{\dbinom{j}{p}}_{=\dfrac{j!}{p!\left( j-p\right) !} }\underbrace{\dbinom{n}{i}^{-1}}_{=\dfrac{i!\left( n-i\right) !}{n!}}\left( -1\right) ^{p} \begin{cases} 1, & \text{if }n-i=j-p;\\ 0, & \text{if }n-i<j-p \end{cases}$

$=\dfrac{j!}{p!\left( j-p\right) !}\cdot\dfrac{i!\left( n-i\right) !} {n!}\cdot\left( -1\right) ^{p} \begin{cases} 1, & \text{if }n-i=j-p;\\ 0, & \text{if }n-i<j-p \end{cases}$

$=\left( -1\right) ^{p}\dfrac{i!j!}{n!p!}\cdot\underbrace{\dfrac{\left( n-i\right) !}{\left( j-p\right) !} \begin{cases} 1, & \text{if }n-i=j-p;\\ 0, & \text{if }n-i<j-p \end{cases} }_{\substack{= \begin{cases} 1, & \text{if }n-i=j-p;\\ 0, & \text{if }n-i<j-p \end{cases} \\\text{(since }\dfrac{\left( n-i\right) !}{\left( j-p\right) !}=1\text{ in the case when }n-i=j-p\text{,}\\\text{whereas in the other case both sides are }0\text{)}}}$

$=\left( -1\right) ^{p}\dfrac{i!j!}{n!p!}\cdot \begin{cases} 1, & \text{if }n-i=j-p;\\ 0, & \text{if }n-i<j-p \end{cases}$

$=\left( -1\right) ^{p}\dfrac{i!j!}{n!p!}\cdot \begin{cases} 1, & \text{if }p=i+j-n;\\ 0, & \text{if }p<i+j-n \end{cases}$

(since $n-i=j-p$ is equivalent to $p=i+j-n$)

$=\left( -1\right) ^{i+j-n}\dfrac{i!j!}{n!p!}\cdot\underbrace{ \begin{cases} 1, & \text{if }p=i+j-n;\\ 0, & \text{if }p<i+j-n \end{cases} }_{\substack{=p!\left[ X^{i+j-n}\right] P\\\text{(by the equality (0))}}}$

(since $\left( -1\right) ^{p}=\left( -1\right) ^{i+j-n}$ in the case when $p=i+j-n$, whereas in the other case both sides are $0$)

$=\left( -1\right) ^{i+j-n}\dfrac{i!j!}{n!p!}\cdot p!\left[ X^{i+j-n} \right] P=\left( -1\right) ^{i+j-n}\dfrac{i!j!}{n!}\left[ X^{i+j-n} \right] P$.

Thus, Theorem 1 is proven.