5
$\begingroup$

How do you prove $\sum_{j=0}^n (x)^j (-1)^{n-j} \left\{{n \atop j}\right\} = x^n,$ where $(x)^j=x(x+1)...x(x+j-1)$ and $\left\{{n \atop j}\right\}$ is a Stirling number of the second kind?

  • 0
    @FuZxxl Yes, rising factorials.2011-03-05

4 Answers 4

12

To remove the $(-1)^{n-j}$ term we replace $x$ by $-x$ and prove

$x^n = \sum_{j=0}^n \left\{ { n \atop j } \right\} (x)_j , \quad (1)$

where $(x)_j = x(x-1)(x-2) \cdots (x-j+1)$ and $(x)_0 = 1.$

We proceed by induction. Note that $(1)$ is true for $n=0$ and so we take $n>0$ and assume $(1)$ is true for $n-1.$

$\begin{align*} x^n &= x \cdot x^{n-1} \\ &= x \sum_{j=0}^{n-1} \left\{ { n-1 \atop j } \right\} (x)_j \\ &= \sum_{j=0}^{n-1} \left\{ { n-1 \atop j } \right\} (x)_j (x-j + j) \\ &= \sum_{j=0}^{n-1} \left\{ { n-1 \atop j } \right\} (x)_{j+1} + \sum_{j=0}^{n-1} j \left\{ { n-1 \atop j } \right\} (x)_j \\ &= \sum_{j=1}^n \left\{ { n-1 \atop j-1 } \right\} (x)_j + \sum_{j=0}^{n-1} j \left\{ { n-1 \atop j } \right\} (x)_j \\ &= \sum_{j=0}^n \left\{ { n \atop j } \right\} (x)_j. \end{align*}$

The last equality follows from the recurrence relation for the Stirling numbers of the second kind:

$ \left\{ { n \atop j } \right\} = \left\{ { n-1 \atop j-1 } \right\} + j \left\{ { n-1 \atop j } \right\}.$

  • 0
    @Fan Zhang: I'm glad you like it. However, unfortunately, I can't claim it as mine; it's just a standard argument that I happened to know.2011-03-05
11

Use the definition! (Note we prove equation (1) which appears in Derek's answer).

Stirling numbers, $\displaystyle \left\{ { n \atop k } \right\}$ are the number of ways to partition set of $n$ items into $k$ non-empty subsets:

Let $\displaystyle x$ be any positive integer $\displaystyle \gt n$.

Let us count the number of ways to choose an $\displaystyle n$-tuple $\displaystyle (a_1, a_2, \dots, a_n)$, by picking the $\displaystyle a_i$ from $\{1,2, \dots, x\}$ with replacement.

The total possibilities is $\displaystyle x^n$.

Now count the same, by counting tuples with exactly $\displaystyle j$ distinct colours, and adding up varying $\displaystyle j$ from $\displaystyle 0$ to $\displaystyle n$.

Since the identity is a polynomial in $\displaystyle x$, and is satisfied by infinitely many integers $\displaystyle x$, this is true even if $\displaystyle x$ is made complex.

5

There's a simple but not very well-known formula on row sums for number triangles that can be applied here. I believe it is due to Neuwirth. Suppose you have a triangle of numbers $R(n,k)$ with $R(0,0) = 1$ and, for $n \geq 1$, satisfying R(n,k) = (\alpha (n-1) + \beta k + \gamma) R(n-1,k) + (\alpha' (n-1) + \beta' (k-1) + \gamma') R(n-1,k-1). There are several interesting number triangles that are special cases, such as the binomial coefficients and both kinds of Stirling numbers.

Anyway, the formula is that if \beta + \beta' = 0 then \sum_{k=0}^n R(n,k) = \prod_{i=0}^{n-1} \left((\alpha + \alpha')i + \gamma + \gamma'\right).

It is easy to verify that $R(n,k) = \left\{ { n \atop k } \right\} x^{\underline{k}}$ satisfies the above recurrence with \beta = 1, \beta' = -1, \gamma' = x and all other parameters $0$. Thus the row sum formula yields Derek's reformulation of the problem (Eq. (1)):

$\sum_{k=0}^n \left\{ { n \atop k } \right\} x^{\underline{k}} = \prod_{i=0}^{n-1} x = x^n.$

0

The Stirling numbers of the second kind represent the marked combinatorial species $\mathcal{Q} = \mathfrak{P}(\mathcal{U}\;\mathfrak{P}_{\ge 1}(\mathcal{Z})).$ This immediately implies that the bivariate generating function of these numbers is $Q(z,u) = \exp(u(\exp(z)-1)).$

Hence we have ${n\brace j} = n! [z^n] [u^j] \exp(u(\exp(z)-1)).$ This gives the following expression for the sum: $ \sum_{j=0}^n x^{(j)} (-1)^{n-j} {n\brace j} = (-1)^n n! [z^n] \sum_{j=0}^n (-1)^j x^{(j)} [u^j] \exp(u(\exp(z)-1)) \\= (-1)^n n! [z^n] \sum_{j=0}^n (-1)^j x^{(j)} \frac{(\exp(z)-1)^j}{j!} = (-1)^n n! [z^n] \sum_{j=0}^n (-1)^j {x+j-1\choose j} (\exp(z)-1)^j.$ Now observe that we can extend the sum to infinity since $(\exp(z)-1)^j$ produces terms in $z$ with exponent larger than $n$ when $j>n$ that do not contribute to $[z^n]$, giving $(-1)^n n! [z^n] \sum_{j=0}^\infty (-1)^j {x+j-1\choose j} (\exp(z)-1)^j.$ Using the Newton binomial this becomes $(-1)^n n! [z^n] \frac{1}{(1-(1-\exp(z)))^x} = (-1)^n n! [z^n] \exp(-zx) = (-1)^n n! (-1)^n \frac{x^n}{n!} = x^n, \quad\text{QED.}.$