# Trying to prove a congruence for Stirling numbers of the second kind

This a repost of a question I asked at Stack Exchange, but I got no answer so far, so I am trying here, even though it may not suit the "research level" requirement.

Proposition: When $n$ and $m$ are 2 natural integers such that $n-m$ is odd, then the following congruence holds for Stirling number of the second kind ${n \brace m}$ : $${n \brace m}\equiv0 \ \mod \frac{m(m+1)}{2}$$
I have not succeeded to prove it, and I am wondering whether a proof (may be a combinatorial one?) has already been given. I would welcome any help or indication on this. Thank you in advance.

Here is the path I have followed so far. I suppose that $n$ is odd and I try to show the following equivalent statement for all $m$ $${n+m \brace m}\equiv0 \ \mod \frac{m(m+1)}{2}$$ I make use of the following recurrence relations $${n+m \brace m} =m{n+m-1 \brace m}+{n+m-1 \brace m-1}$$ $$\sum_{i=1}^{i=n}m^{i}{n-i+m-1 \brace m-1} ={n+m \brace m}-{n+m-1 \brace m-1}$$ The first one is basic and the second one is easily derived from the first one.

Then, with the notation $S_i(m)=\sum_{j=1}^{j=m}j^{i}$ , I can show that $${n+m \brace m} =\frac{1}{n}\sum_{i=1}^{i=n}S_i(m){n-i+m \brace m}$$ The proof of this third relation is by double induction on $n$ and $m$: It is easy to see that is true for all $n$ when $m=1$, and for all $m$ it is obviously true for $n=1$. Then, I use the first and second relations above and also $m^{i}=S_i(m)-S_i(m-1)$ to complete the proof of the third relation by induction.

Then, I would like to show the proposed congruence by induction on $n$ ($m$ being fixed) with the help of the third relation.

The congruence is true for $n=1$, and my induction hypothesis is that it is true for all ${k+m \brace m}$ where $k\lt n$ is odd.

In the third relation the sum is divisible by $\frac{m(m+1)}{2}$, because, when $i$ is odd $S_i(m)$ is divisible by $\frac{m(m+1)}{2}$ (this is shown here), and when $i$ is even then $n-i$ is odd, since $n$ is odd, and by induction hypothesis ${n-i+m \brace m}$ is divisible by $\frac{m(m+1)}{2}$

Eventually I obtain that for odd $n$ $$n{n+m \brace m}\equiv0 \ \mod \frac{m(m+1)}{2}$$ which is almost, but not quite, what I wanted. Is this a dead end?

• There is a similar result for Stirling numbers of the first kind. See Corollary 3.4 of math.mit.edu/~rstan/papers/cycles.pdf. Dec 28 '14 at 21:52
• Ok. There is probably a proof similar to that of Gjergji, using the analogous generating function. Dec 29 '14 at 7:03

Lemma: The power series $$\frac{1}{(1-x)(1-2x)\cdots (1-kx)}$$ is even $\pmod{k+1}$ when $k+1$ is odd, and even $\pmod{\frac{k+1}{2}}$ when $k+1$ is even.
Proof: By grouping terms, when $k+1$ is odd we have $$\frac{1}{(1-x)(1-2x)\cdots (1-kx)}\equiv \frac{1}{(1-x^2)(1-4x^2)\cdots (1-\frac{k^2x^2}{4})}\pmod{k+1}$$ and when $k+1$ is even we have $$\frac{1}{(1-x)(1-2x)\cdots (1-kx)}\equiv \frac{1}{(1-x^2)(1-4x^2)\cdots (1-\frac{(k-1)^2x^2}{4})}\pmod{\frac{k+1}{2}}. \blacksquare$$
For your problem, notice that $$\sum_{n=0}^{\infty}S(n+m,m)x^n=\frac{1}{(1-x)(1-2x)\cdots(1-mx)}$$ so by the lemma the odd coefficients vanish $\pmod{m}$ and $\pmod{\frac{m+1}{2}}$ when $m$ is odd and similarly when $m$ is even. Either way you get the desired result $\pmod{\frac{m(m+1)}{2}}$ because $\gcd(m,m+1)=1$.