How to prove recursion formulas for Stirling numbers? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T00:45:13Z http://mathoverflow.net/feeds/question/108896 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108896/how-to-prove-recursion-formulas-for-stirling-numbers How to prove recursion formulas for Stirling numbers? Melania 2012-10-05T07:23:41Z 2012-10-05T18:28:35Z <ol> <li>Put $B(n,k)=k! S(n,k)$, here $S(n,k)$ be the Srirling numbers of second kind. </li> </ol> <p>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$$</p> <ol> <li>Put $T(n,i)=\displaystyle \sum_{j=i}^n (-1)^{j-i} 2^{n-j} B(n,j) {j-1 \choose i-1}$. </li> </ol> <p>Prove that </p> <p>$$\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.$$</p> http://mathoverflow.net/questions/108896/how-to-prove-recursion-formulas-for-stirling-numbers/108929#108929 Answer by Ira Gessel for How to prove recursion formulas for Stirling numbers? Ira Gessel 2012-10-05T15:57:16Z 2012-10-05T18:28:35Z <p>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!$.</p> <p>Multiply the left side by $x^n/n!$ and sum on $n$ from 1 to $\infty$. We obtain <code>\begin{align*} \sum_{j=i+1}^\infty\frac{(-1)^{j+1-i}}{j-i} (e^x-1)^j &amp;=\sum_{k=1}^\infty \frac{(-1)^{k-1}}{k}(e^x-1)^{i+k}\\ &amp;=(e^x-1)^i \sum_{k=1}^\infty \frac{(-1)^{k-1}}{k}(e^x-1)^{k}\\ &amp;=(e^x-1)^i\log(1+(e^x-1))= x(e^x-1)^i\\ &amp;=\sum_{n=1}^\infty n\cdot i!\, S(n-1,i)\frac{x^n}{n!}. \end{align*}</code></p> <p>It seems likely that a similar approach will work for the second formula, but I have not tried it.</p>