This a repost of a question I [asked](https://math.stackexchange.com/questions/1061534/trying-to-prove-a-congruence-for-stirling-numbers-of-the-second-kind) 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](https://math.stackexchange.com/questions/1061534/trying-to-prove-a-congruence-for-stirling-numbers-of-the-second-kind)), 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?



Trying to prove a congruence for Stirling numbers of the second kind
Here is a quick generating function argument. Start with the following lemma



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


