Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 11 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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