Combinatorial identity with connection coefficients and falling factorial $\langle i x\rangle_n$

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

This is a note on Fedor Petrov's identity

$$\sum_{i=0}^j (-1)^{j-i}\frac{f(i)}{i!(j-i)!}=[t^j]f(t),$$

conjured by him from Lagrange interpolation, and its relation to Newton series, which is an expansion of suitable functions in the basis of the falling factorials, a.k.a. the Stirling polynomials of the first kind $ST1_n(x)$, or the binomial coefficients

$$\frac{ST1_n(x)}{n!} = \frac{1}{n!}\sum_{j=0}^n S_{n,j}x^j = \binom{x}{n},$$

the basis Grinberg assumes in his analysis. This makes connections to the classic finite difference calculus, the Euler diff op, and the Stirling polynomials of the second kind of import in combinatorics.

With $D$ the derivative w.r.t. $x$, the generalized Dobinski identity is

$$e^{-x}f(xD)e^x =e^{-x} \sum_{n \geq 0}f(n) \frac{x^n}{n!} = \sum_{n \geq 0} (-1)^n\sum_{j=0}^n \binom{n}{j} (-1)^j f(j) \frac{x^n}{n!}$$

where if one of the two series is convergent so is the other (this is the Euler transformation for e.g.f.s, in umbral notation $e^{-x} e^{a.x} = e^{-(1-a.)x}$).

Normal ordering of the exponentiated Euler, or state number, op $(xD)^n$ defines the Stirling polynomials of the second kind as

$$(xD)^n = ST2_n(:xD:)$$

where, by definition, $:xD:^k = x^kD^k,$ so

$$e^{-x}f(xD)e^x =e^{-x} f(ST2.(:xD:)) e^x$$

$$ = f(ST2.(x)) = \sum_{n \geq 0} (-1)^n \frac{x^n}{n!} \sum_{j=0}^n \binom{n}{j} (-1)^j f(j) .$$

In particular, for $f(x) = x^m$, this gives

$$ (ST2.(x))^m = ST2_m(x)= \sum_{j=0}^m ST2_{m,j}x^j = \sum_{n \geq 0} (-1)^n \frac{x^n}{n!} \sum_{j=0}^n \binom{n}{j} (-1)^j j^m,$$

implying, for $n \gt m$

$$\sum_{j=0}^n \binom{n}{j} (-1)^j j^m = 0,$$

so, for any polynomial $P_K(x)$ of order $K$ for $n \gt K$,

$$\sum_{j=0}^n \binom{n}{j} (-1)^j P_K(j) = 0.$$

The set of Stirling polynomials of the first kind is the umbral inverse set for those of the second kind under umbral substitution / composition; that is,

$$ST2_n(ST1.(x))= x^n = ST1_n(ST2.(x))$$

(see this MO-Q for a one line proof), so umbral substitution into the Dobinski relation gives the Newton series, convergent for a wide class of functions, including all polynomials,

$$f(ST2.(ST1.(x))) = f(x) = \sum_{n \geq 0} (-1)^n \binom{x}{n} \sum_{j=0}^n \binom{n}{j} (-1)^j f(j) .$$

Note for $m =0,1,2,\ldots$ with the natural convention

$$\frac{1}{(-m-1)!}:=\lim_{x\to -m} \frac{1}{\Gamma(x)}=0,$$

we have the well known identity

$$f(m) = \sum_{n = 0}^m (-1)^n \binom{m}{n} \sum_{j=0}^n (-1)^j \binom{n}{j} f(j).$$

Taking derivatives of the Newton series gives

$$\frac{D_{x=0}^m}{m!}f(x) = \sum_{n \geq 0} (-1)^n \frac{ST1_{n,m}}{n!} \sum_{j=0}^n \binom{n}{j} (-1)^j f(j) . $$

This implies, as indicated also in the prior analysis, for $f(x) = P_K(x)$ a polynomial of order $K$ and $m > K$,

$$\sum_{j=0}^m \binom{n}{j} (-1)^j P_K(j)=0,$$

so we can truncate the Newton series to give

$$P_K(x) = \sum_{n =0}^K (-1)^n \binom{x}{n} \sum_{j=0}^n \binom{n}{j} (-1)^j P_K(j) , $$

and

$$\frac{D_{x=0}^m}{m!}P_K(x) = \sum_{n = 0}^K (-1)^n \frac{ST1_{n,m}}{n!} \sum_{j=0}^n \binom{n}{j} (-1)^j P_K(j) . $$

For $m=K$,

$$[x^K]P_K(x) = \frac{D_{x=0}^K}{K!}P_K(x) = \sum_{n = 0}^K (-1)^n \frac{ST1_{n,K}}{n!} \sum_{j=0}^n \binom{n}{j} (-1)^j P_K(j)$$

$$ = (-1)^K \frac{1}{K!} \sum_{j=0}^K \binom{K}{j} (-1)^j P_K(j) . $$

since $ST1_{n,K}=0$ for $K >n$ and $ST1_{K,K}=1$.

This is Petrov's identity.

Aside:

Let $\hat{f}_K(x)$ be the truncation of the Taylor series expansion of $f(x)$ about the origin at the $K$-th term. Then

$$\frac{D_{x=0}^K}{K!}f(x) = (-1)^K \frac{1}{K!} \sum_{j=0}^K \binom{K}{j} (-1)^j \hat{f}_K(j) . $$

Another method of proof of Petrov's identity and a generalization:

Any Sheffer polynomial sequence $S_n(x)$ is a basis for all polynomials, and every SPS has an umbral inverse sequence $\hat{S}_n(x)$ defined by

$$ S_n(\hat{S}.(x)) = x^n = \hat{S}_n(S.(x))$$

and a lowering (destruction/annihilation) diff op defined by

$$L_S \; S_n(x) = n \; S_{n-1}(x).$$

The e.g.f. of a binomial SPS has the form

$$e^{B.(x)t} = e^{xh(t)},$$

and that of its umbral inverse sequence is

$$e^{\hat{B}.(x)t} = e^{xh^{-1}(t)},$$

where $h(t)$ and $h^{-1}(t)$ are a compositionally inverse pair of analytic functions (or formal Taylor series) about the origin, i.e.,

$$h(h^{-1}(t))=t = h^{-1}(h(t))$$

with $h(0) =0$ and $h'(0) \neq 0$; hence, the umbral inversion relation

$$e^{S.(\hat{S}.(x))t} = e^{\hat{S}.(x)h(t)} = e^{xh^{-1}(h(t))} = e^{xt}$$

holds.

The lowering op for $B_n(x)$ is

$$L_B = h^{-1}(D_x)$$

since

$$h^{-1}(D_x) e^{B.(x)t} = h^{-1}(D_x)e^{x h(t)} = h^{-1}(h(t))e^{x h(t)} = t e^{x h(t)} = t e^{B.(x)t}.$$

For any binomial SPS $B_n(0) = 0^n = \delta_n$, the Kronecker delta, where by convention $0^0 =1$, and the sequence of monomials $M_n(x) = x^n$ is a binomial SPS with $L_M = D_x$ , so we have the parallelism

$$P_K(x) = \sum_{j=0}^K \tilde{p}_{K,j} \frac{B_j(x)}{j!} = \sum_{j=0}^K p_{K,j} \frac{x^j}{j!}$$

with

$$L_M^m P_K(x)|_{x=0} = D_x^m P_K(x) |_{x=0}= p_{K,m}$$

and

$$L_{B}^m P_K(x)|_{x=0} = (h^{-1}(D_x))^m P_K(x) |_{x=0} = \tilde{p}_{K,m}.$$

The Stirling polynomials of the first and second kinds are binomial SPSs with the e.g.f.s

$$e^{ST1.(x)t} = e^{x\ln(1+t)} = (1+t)^x$$

and

$$e^{ST2.(x)t} = e^{x(e^t-1)},$$

so

$$L_{ST1} = e^{D_x}-1 ,$$

the forward finite difference op. Then

$$L_{ST1} \binom{x}{n}|_{x=0} = L_{ST1} \frac{ST1_n(x)}{n!}|_{x=0} = \binom{0}{n-1} = \delta_{n-1},$$

so with

$$P_K(x) = \sum_{j=0}^K \bar{p}_{K,j} \binom{x}{j},$$

then

$$\bar{p}_{K,m} = L_{ST1}^m P_K(x) |_{x=0} = (e^{D_x}-1)^m P_K(x) |_{x=0}$$

$$ =(-1)^m \sum_{j=0}^m (-1)^j \binom{m}{j}e^{jD_x} P_K(x)|_{x=0}=(-1)^m \sum_{j=0}^m (-1)^j \binom{m}{j} P_K(x+j)|_{x=0}$$

$$ = (-1)^m \sum_{j=0}^m (-1)^j \binom{m}{j} P_K(j).$$

For $m = K$ and dividing by $K!$, this is Petrov's identity from Lagrange interpolation.

(My last identity is stated on p. 6 of "Rook numbers and the normal ordering problem" by Anna Varvak (https://arxiv.org/abs/math/0402376) without proof but referencing Stanley's Enumerative Combinatorics Vol 1.)