# How to prove recursion formulas for Stirling numbers?

1. Put $B(n,k)=k! S(n,k)$, here $S(n,k)$ be the Srirling numbers of second kind.

Prove that $$\sum_{j=i+1}^n \frac{(-1)^{j+1-i}}{j-i} B(n,j)= n B(n-1,i),i=0,1,\ldots,n-1$$

1. Put $T(n,i)=\displaystyle \sum_{j=i}^n (-1)^{j-i} 2^{n-j} B(n,j) {j-1 \choose i-1}$.

Prove that

$$\sum_{j=i+1}^n \frac{1-(-1)^{j-i}}{2(j-i)}T(n,j)= n T(n-1,i),i=0 \ldots n-1.$$

-
You should go to Stack Exchange where more or less the same question has already been discussed: math.stackexchange.com/questions/39042/… –  Nick Gill Oct 5 '12 at 10:14
@Nick: To me this question Melania has asked looks a lot harder than the one you link. The way I'd try to attack the above (given my bias towards topological combinatorics) is to try to define posets with these alternating sums as their Moebius functions and try to find a lexicographic shelling for the posets so that the simplified formulas are counting descending chains. But the denominators make this seem very tricky. Without the denominator interferance, the first alternating sum would be (up to some shifting) the Euler characteristic of a skeleta of a type A Coxeter complex. –  Patricia Hersh Oct 5 '12 at 11:04
Maybe I should ask if I'm missing something -- at least I didn't see how to do this easily. It seemed like the recurrence to which Nick refers (and which I've taught in my combinatorics class) involves letting $n$ grow, whereas this question is more about letting $k$ grow. –  Patricia Hersh Oct 5 '12 at 15:06
Patricia, you're quite right, I commented in haste and I shall now repent at leisure... –  Nick Gill Oct 8 '12 at 13:55
Here is a proof of the first formula. We use the exponential generating function $\sum_{n=0}^\infty S(n,k) x^n/n! = (e^x-1)^k/k!$.
Multiply the left side by $x^n/n!$ and sum on $n$ from 1 to $\infty$. We obtain \begin{align*} \sum_{j=i+1}^\infty\frac{(-1)^{j+1-i}}{j-i} (e^x-1)^j &=\sum_{k=1}^\infty \frac{(-1)^{k-1}}{k}(e^x-1)^{i+k}\\ &=(e^x-1)^i \sum_{k=1}^\infty \frac{(-1)^{k-1}}{k}(e^x-1)^{k}\\ &=(e^x-1)^i\log(1+(e^x-1))= x(e^x-1)^i\\ &=\sum_{n=1}^\infty n\cdot i!\, S(n-1,i)\frac{x^n}{n!}. \end{align*}