Convolution Identity for Stirling Numbers

Question

Trying to prove the following identity (obtained from a problem in statistical mechanics):

\begin{equation} S(\ell, m) = \sum_{k=m}^{\ell}\binom{k}{m} \sum_{i=0}^{k}(-1)^{\ell+i} \,S(\ell + i - m, k)\, s(k, i) \,\binom{\ell}{\ell+i-m}, \end{equation}

where $S$ and $s$ denote Stirling numbers of the second and first kind, respectively.

I tested the identity in Mathematica and it yielded true values for $0 \leq m\leq \ell \leq 50$ so I think it's true in general, but I haven't seen it in any relevant texts (I've checked Gould's Combinatorial Identities and Roman's Umbral Calculus).

It also doesn't seem to easily reduce to any standard convolution identities (like 23. and 24. in http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html or 19, 23, 27, or 33 in http://dlmf.nist.gov/26.8#SS4.info)

Could anyone construct a combinatorial proof?

Answer 1

Suppose we seek to verify that

$${n\brace m} = \sum_{k=m}^n {k\choose m} \sum_{q=0}^k (-1)^{n+q} {n+q-m\brace k} (-1)^{k+q} \left[k\atop q\right] {n\choose n+q-m}$$

which is

$${n\brace m} = (-1)^n \sum_{k=m}^n {k\choose m} (-1)^k \sum_{q=0}^k {n+q-m\brace k} \left[k\atop q\right] {n\choose m-q}$$

where presumably $n\ge m.$ We need for the second binomial coefficient that $m\ge q$ so this is

$${n\brace m} = (-1)^n \sum_{k=m}^n {k\choose m} (-1)^k \sum_{q=0}^m {n+q-m\brace k} \left[k\atop q\right] {n\choose m-q}.$$

Observe that the Stirling number of the second kind vanishes when $k\gt n$ so we may extend the summation to infinity, getting

$${n\brace m} = (-1)^n \sum_{k\ge m} {k\choose m} (-1)^k \sum_{q=0}^m {n+q-m\brace k} \left[k\atop q\right] {n\choose m-q}.$$

Recall that

$$\left[k\atop q\right] = [w^q] k! \times {w+k-1\choose k}.$$

Starting with the inner sum we obtain

$$n! \sum_{q=0}^m \frac{1}{(m-q)!} [z^{n+q-m}] (\exp(z)-1)^k [w^q] {w+k-1\choose k} \\ = n! \sum_{q=0}^m \frac{1}{q!} [z^{n-q}] (\exp(z)-1)^k [w^{m-q}] {w+k-1\choose k}.$$

Now when $q\gt m$ the coefficient extractor in $w$ yields zero, hence we may extend the sum in $q$ to infinity:

$$n! \sum_{q\ge 0} \frac{1}{q!} [z^{n-q}] (\exp(z)-1)^k [w^{m-q}] {w+k-1\choose k}.$$

We thus obtain

$$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (\exp(z)-1)^k \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{m+1}} {w+k-1\choose k} \sum_{q\ge 0} \frac{1}{q!} z^q w^q \; dw \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (\exp(z)-1)^k \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{m+1}} {w+k-1\choose k} \exp(zw) \; dw \; dz.$$

Preparing the outer sum we obtain

$$\sum_{k\ge m} {k\choose m} (-1)^k (\exp(z)-1)^k {w+k-1\choose k} \\ = \sum_{k\ge m} {k\choose m} (-1)^k (\exp(z)-1)^k [v^k] \frac{1}{(1-v)^w}.$$

Note that for a formal power series $Q(v)$ we have

$$\sum_{k\ge m} {k\choose m} (-1)^{k-m} u^{k-m} [v^k] Q(v) = \frac{1}{m!} \left.(Q(v))^{(m)}\right|_{v=-u}.$$

We get for the derivative in $v$

$$\left(\frac{1}{(1-v)^w}\right)^{(m)} = m! {w+m-1\choose m} \frac{1}{(1-v)^{w+m}}.$$

Substituting $u=\exp(z)-1$ yields

$$m! {w+m-1\choose m} \exp(-(w+m)z).$$

Returning to the double integral we find

$$\frac{(-1)^n\times n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (\exp(z)-1)^m (-1)^m \\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{m+1}} \exp(zw) {w+m-1\choose m} \exp(-(w+m)z) \; dw \; dz \\ = \frac{(-1)^n\times n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (\exp(z)-1)^m (-1)^m \exp(-mz) \\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{m+1}} {w+m-1\choose m} \; dw \; dz \\ = \frac{(-1)^n\times n!}{2\pi i \times m!} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (\exp(z)-1)^m (-1)^m \exp(-mz) \; dz \\ = \frac{(-1)^n\times n!}{2\pi i \times m!} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1-\exp(-z))^m (-1)^m \; dz \\ = \frac{(-1)^n\times n!}{2\pi i \times m!} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (\exp(-z)-1)^m \; dz.$$

Finally put $z=-v$ to get

$$-\frac{(-1)^n\times n!}{2\pi i \times m!} \int_{|v|=\epsilon} \frac{(-1)^{n+1}}{v^{n+1}} (\exp(v)-1)^m \; dv \\ = \frac{n!}{2\pi i \times m!} \int_{|v|=\epsilon} \frac{1}{v^{n+1}} (\exp(v)-1)^m \; dv.$$

This is

$$n! [v^n] \frac{(\exp(v)-1)^m}{m!} = {n\brace m}$$

and we have the claim.

Answer 2

Note: This is a rather challenging identity. The following is inspired by an in-depth analysis of the answer of @MarkoRiedel which was of great help to overcome some difficulties.

This answer is based upon the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write e.g. \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

Here we use D. Knuth's notational convention and write $\left[n\atop k\right]$ for the unsigned Stirling numbers of the first kind and ${n\brace k}$ for the Stirling numbers of the second kind.

From generating functions we get \begin{align*} \left[k\atop i\right]=[z^k]n!\binom{z+n-1}{n}\qquad\text{and}\qquad {n\brace k}=n![z^n]\frac{\left(e^z-1\right)^k}{k!}\\ \end{align*}

The following is valid for $0\leq m\leq l$

\begin{align*} {l\brace m}=\sum_{k=m}^l\binom{k}{m}\sum_{i=0}^k(-1)^{l+k}{l+i-m\brace k}\left[k\atop i\right]\binom{l}{l+i-m} \end{align*}

Note that here is the sign $(-1)^{l+k}$ whereas in OPs formula the sign is $(-1)^{l+i}$. This is due to $s(k,i)=(-1)^{k+i}\left[k\atop i\right]$.

We obtain

\begin{align*} \sum_{k=m}^l&\binom{k}{m}\sum_{i=0}^k(-1)^{l+k}{l+i-m\brace k}\left[k\atop i\right]\binom{l}{l+i-m}\\ &=\sum_{k=m}^l\binom{k}{m}\sum_{i=0}^m(-1)^{l+k}{l-i\brace k}\left[k\atop m-i\right]\binom{l}{i}\tag{1}\\ &=\sum_{k\geq m}\binom{k}{m}\sum_{i\geq 0}(-1)^{l+k}(l-i)![z^{l-i}]\frac{\left(e^z-1\right)^k}{k!} [u^{m-i}]k!\binom{u+k-1}{k}\binom{l}{i}\tag{2}\\ &=\sum_{k\geq m}\binom{k}{m}\sum_{i\geq 0}(-1)^{l+k}[z^{l-i}]\left(e^z-1\right)^k [u^{m-i}]\binom{-u}{k}(-1)^k\frac{l!}{i!}\tag{3}\\ &=(-1)^ll!\sum_{k\geq m}\binom{k}{m}[z^{l}]\left(e^z-1\right)^k [u^{m}][t^k](1+t)^{-u}\sum_{i\geq 0}\frac{(zu)^i}{i!}\tag{4}\\ &=(-1)^ll![z^{l}][u^{m}]e^{zu}\sum_{k\geq m}\binom{k}{m}\left(e^z-1\right)^k [t^k](1+t)^{-u}\tag{5}\\ &=(-1)^ll![z^{l}][u^{m}]e^{zu}\left(e^z-1\right)^m\frac{1}{m!}D_t^m\left.(1+t)^{-u}\right|_{t=e^z-1}\tag{6}\\ &=(-1)^ll![z^{l}][u^{m}]e^{zu}\left(e^z-1\right)^m(-1)^m\binom{u+m-1}{m}\left.(1+t)^{-(u+m)}\right|_{t=e^z-1}\tag{7}\\ &=(-1)^{l}l![z^{l}]\left(e^z-1\right)^me^{-mz}(-1)^m[u^{m}]\binom{u+m-1}{m}\tag{8}\\ &=(-1)^ll![z^{l}]\left(e^{-z}-1\right)^m\frac{1}{m!}\tag{9}\\ &=l![z^{l}]\frac{\left(e^{z}-1\right)^m}{m!}\tag{10}\\ &={l\brace m} \end{align*} and the claim follows.

Comment:

• In (1) we set the upper limit of the inner sum to $m$ since $k\geq m$ and therefore $\binom{l}{l+i-m}=0$ for $i\geq m$. We also change the order of the inner sum by $i\rightarrow m-i$.

• In (2) we apply the coefficient of operator twice to the Stirling numbers of the first and second kind. We also set the upper limit of both sums to $\infty$ without changing anything since we are adding zeros only.

• In (3) we do some cancellation and use the binomial identity $$\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$$

• In (4) we do some rearrangements and apply the rule \begin{align*} [z^{p-q}]A(z)=[z^p]z^qA(z) \end{align*}

• In (5) we do some rearrangements and expand the exponential series.

• In (6) we recall the substitution rule of the coefficient of operator \begin{align*} A(z)=\sum_{k\geq 0} a_k z^k=\sum_{k\geq 0} z^k [t^k]A(t) \end{align*} Using the differential operator $D_z:=\frac{d}{dz}$ and apply it $m$ times we obtain \begin{align*} D_z^mA(z)&=\sum_{k\geq m} k(k-1)\cdots (k-m+1)a_k z^{k-m}\\ &=m!\sum_{k\geq m}\binom{k}{m}a_kz^{k-m}\\ &=m!\sum_{k\geq m}\binom{k}{m}z^{k-m}[t^k]A(t) \end{align*}

It follows using the substitution $t:= e^z-1$ \begin{align*} \sum_{k\geq m}\binom{k}{m}\left(e^z-1\right)^{k-m}[t^k](1+t)^{-u} =\frac{1}{m!}D_t^m\left.(1+t)^{-u}\right|_{t=e^z-1} \end{align*}

• In (7) we do the differentiation.

• In (8) we substitute and simplify

• In (9) we select the coefficient of $u^m$ from the polynomial $\binom{u+m-1}{m}$ in $u$ and simplify the expression.

• In (10) we substitute $z\rightarrow -z$.