6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ There's lots of material on generalized Stirling numbers of the first and second kind that might contain the identity. $\endgroup$ – Tom Copeland Dec 2 '16 at 1:59
  • $\begingroup$ At least some signs are missing. I get $-3/10 x$ for $j=3$, $k=3$, $n=5$ and $m=1$. $\endgroup$ – darij grinberg Dec 2 '16 at 6:28
  • $\begingroup$ 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}$. $\endgroup$ – darij grinberg Dec 2 '16 at 6:33
  • $\begingroup$ Ah yes, this boils down to a finite difference argument. $\endgroup$ – darij grinberg Dec 2 '16 at 6:35
  • $\begingroup$ @darijgrinberg can you elaborate? None of the finite difference arguments I have seen involve two binomial coefficients $\binom{k}{i}\binom{j}{i}$ $\endgroup$ – Nick R Dec 2 '16 at 7:01
9
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

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