Proving function for Stirling Numbers of the Second Kind

Question

I need to proof the following formula for Stirling Numbers of the Second Kind:

$\sum\limits_{n \geq 0} S(n,k) x^n = \frac{x^k}{(1-x)(1-2x)\cdots(1-kx)}$

It is used widely around formularies but I neither have found any proof nor was I able to figure it out on my own.

Could you please help me finding a solution?

Thank you in advance!

Answer 1

This is set out in the initial part of section 1.6 of Geneatingfunctionology with the result in equation 1.6.5.

In essense, you start with the recurrence

$$S(n,k) = S(n-1,k-1) + kS(n-1,k)$$

with $S(0,0)=1$. Of the natural generation functions which might express this, the simplest which deals with the factor of $k$ is likely to be of the form

$$B_k(x) = \sum_n S(n,k) x^n$$

which with the recurrence leads to

$$B_k(x) = xB_{k-1}(x) + kxB_k(x) = \frac{x}{1-kx} B_{k-1}(x)$$

for $k \ge 1$; $B_0(x)=1$. That in turn leads to the desired formula by multiplying successive terms.

Answer 2

Hmm, I cannot see the problem which came up in the comments. If we assume simply an error in the notation and that the actually the Stirling numbers 2'nd kind are meant (as verbally exposed in the question) then the identity holds. This can even be checked simply using negative integer $x$ and computing Eulersums of appropriate order.
Let's write S2 the matrix of that numbers as
$ \qquad \small \begin{array} {rrrrrrr} 1 & . & . & . & . & . & . & . \\ 1 & 1 & . & . & . & . & . & . \\ 1 & 3 & 1 & . & . & . & . & . \\ 1 & 7 & 6 & 1 & . & . & . & . \\ 1 & 15 & 25 & 10 & 1 & . & . & . \\ 1 & 31 & 90 & 65 & 15 & 1 & . & . \\ 1 & 63 & 301 & 350 & 140 & 21 & 1 & . \\ 1 & 127 & 966 & 1701 & 1050 & 266 & 28 & 1 \\ \ldots & \end{array} $
where we use zero-based row- and columnindexes.

Then the problem can be restated as summing by building the dot product of one column by one row vector $V(x) = [1,x,x^2,x^3,...]$ with manageable (ideally infinite) dimension.

The numbers along a column can be seen as composed by finite compositions of geometric series.

Column 0 is $[1,1,1,1,1,...]$ and the dot-product with the V(x)-vector is then $V(x)*S2[,0] = {1 \over 1-x}$

Column 1 is $[1-1,2-1,4-1,8-1,16-1,...]$ and the dot-product with the V(x)-vector is then $V(x)*S2[,1] = {1 \over 1-2x} - {1 \over 1-x} = { (1-1x) - (1-2x) \over (1-1x)(1-2x) } = {x \over (1-1x)(1-2x) }$

One needs the simple composition of the other columns (see for instance in wikipedia) to see more examples for that decompositions, and also a general description for that compositions (where the text is:"Another explicit expanding of the recurrence-relation(...)").
I think the idea behind that homework-assignment was, that the student should find the compositions of powers such that the problem is ocnverted to describe the (finite) composition of closed forms of geometric series.