# Convolution Identity for Stirling Numbers

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

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

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?

• the first kind Stirlings are signed? or you took away the sign? – Phicar Sep 15 '16 at 2:12
• The Stirling numbers of the first kind in the equation are signed. $s(2,1)$ = -1, for example. – Olukayode Sep 15 '16 at 2:35

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.

• I lack familiarity with the methods to verify this, but I was looking for a derivation which didn't use complex analysis. – Olukayode Sep 15 '16 at 13:47
• Note that we have activity on your post, which I consider an advantage. You can always put a bounty on it in order to bring it to the attention of MSE combinatorics wizards. Another proof may yet appear. – Marko Riedel Sep 15 '16 at 22:17
• Actually this proof is fine. Thank you Marko. – Olukayode Sep 23 '16 at 23:43

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

• This is amazing! I hope it is sound (will check later). (+1). Line 10 seems to be missing a sign flip. – Marko Riedel Sep 24 '16 at 12:14
• @MarkoRiedel: Oh, yes! I see! It's already a litte bit late. But great review Marko! Many thanks. I think the proof is now consistent. – Markus Scheuer Sep 24 '16 at 21:57
• I agree that it has now been vetted. Congratulations on establishing a reference document! Potential readers should really profit from these two different versions. Which of the comments would you like to remove? – Marko Riedel Sep 24 '16 at 21:59
• @MarkoRiedel: Besides that minor technical stuff. The interesting part of the proof was to recognize that it is advantageous to keep the binomial coefficient $\binom{k}{m}$ and use differentiation instead of transforming the sum to start from $k=0$ and working with $\binom{k}{m}=[w^k](1+w)^m$ which led to nowhere. Thanks for that! – Markus Scheuer Sep 24 '16 at 22:03