# How to prove the equality $\sum_{j=0}^n (x)^j (-1)^{n-j} \left\{{n \atop j}\right\} = x^n$?

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?

-
Is your $(x)^j$ the same as $x^\overline{j}?$ – FUZxxl Mar 5 '11 at 10:20
@FuZxxl Yes, rising factorials. – Fan Zhang Mar 5 '11 at 10:22

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\}.$$

-
It's really a cool proof. – Fan Zhang Mar 5 '11 at 13:23
@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. – Derek Jennings Mar 5 '11 at 13:35

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.

-

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.$$

-

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.}.$$

-