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