I'd like to prove the following identity:

$$\sum_{n=0}^{\infty}S\left(n,k\right)\,x^{n}=\frac{x^{k}}{(1-x)(1-2x)\cdots(1-% kx)}$$

(The identity referred from : http://dlmf.nist.gov/26.8#E11)

Rather than using induction, I would like to find another way to prove this identity.

I just superficially understands that the generating function has a intrinsic relation to recurrence relation, and what I know about the recurrence upon Stiring the second kind is:

$$S(n,k) = S(n-1,k-1) + k \cdot S(n-1,k)$$

How can I make up the object identity from this recurrence relation?


We know that if $(n,k) \neq (0,0)$ then we have $S(n, k)= S(n-1, k-1)+kS(n-1,k)$ and we define $S(0,0)=1.$

Let $B_k(x)= \displaystyle \sum_{n\geq 0}S(n, k)x^n$ so multiplying the recurrence above by $x^n$ and summing over $n\geq 0$ we get

$B_{k}(x)= xB_{k-1}(x)+kxB_k(x)$

$\Rightarrow B_k(x)= \dfrac{xB_{k-1}(x)}{1-kx}=\dfrac{x^2B_{k-2}(x)}{(1-kx)(1-(k-1)x)}=\ldots= \dfrac{x^k}{\displaystyle\prod_{r=1}^k(1-rx)}$ thereby establishing the identity.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.