Got a problem onto the TST this year too. Here are the two official solutions; the first one is how I came up with the problem. (I'm told this identity appears in Stanley's Enumerative Combinatorics though; I had niggling doubt this wasn't new...)

Very nice solutions! Errata: MellowMelon wrote:

You seem to want $b_i = c_{i+1} - c_i - 1$ here. MellowMelon wrote: (with $c_{n+1} = n+k+1$), then $b_i$ gives the number of objects between $c_i$ and $c_{i+1}$. Any choice of $(b_1, b_2, \ldots b_n)$ with $b_1 + b_2 + \cdots + b_n = k$ also gives a valid choice of the $c_i$ by letting $c_i = \sum_{j=1}^i b_j$. Should be $c_i = \sum_{j=1}^{i-1} \left(b_j+1\right)$. MellowMelon wrote:

Redundant commata here. If you are searching for this identity in books, the keyword is "Stirling numbers of the second kind".

MellowMelon wrote: Denote by $S_k$ the set of all $n$-term sequences of positive integers $(a_1, a_2, \ldots a_n)$ such that $a_1 + a_2 + \cdots + a_n = k$. Let $b_k = \sum_{S_k} 1^{a_1} 2^{a_2} \cdots n^{a_n}$, with $b_k = 0$ if $k < n$, and let $F_n(x) = b_0 + b_1 x + b_2 x^2 + \cdots$ be a generating function for the $\{b_i\}$. Then \begin{align*} F_n(x) &= (x+x^2+\cdots)(2x+4x^2+\cdots)\cdots (nx+n^2x^2+\cdots), \\ &= \frac{x}{1-x} \frac{2x}{1-2x} \cdots \frac{nx}{1-nx}, \\ &= \frac{n! x^n}{(1-x)(1-2x) \cdots (1-nx)}. \\ \end{align*} I think a slightly more straightforward way to finish (at least for people like me who know next to nothing about generating functions) is to simply get the partial fraction expansion of the denominator. Lemma: Let $Q(x) = (x-r_1)(x-r_2) \cdots (x-r_n)$, with each $r_i$ distinct. Then for all $x \neq r_i$, \[ \frac{1}{Q(x)} = \sum_{i=1}^n \frac{1}{Q'(r_i)(x-r_i)}. \] Proof: If we define \[ f(x) = Q(x) \sum_{i=1}^n \frac{1}{Q'(r_i)(x-r_i)} \] for $x \neq r_i$, then $f(r_i) = \lim_{x \to r_i} f(x)$, then $f$ is a polynomial (since we can cancel the linear factors $\frac{1}{x-r_i}$ with the $Q(x)$.) It is sufficient for us to show that $f(x) = 1$ for all $x$. We note that $f$ has degree at most $n$, and that for each $1 \leq i \leq n$, \[ f(r_i) = \lim_{x \to r_i} Q(x) \frac{1}{Q'(r_i)(x-r_i)} = \frac{1}{Q'(r_i)} \lim_{x \to r_i} \frac{Q(x)}{x-r_i} = \frac{1}{Q'(r_i)} Q'(r_i) = 1, \] (the fourth equality follows from l'Hopital's rule), so the polynomial $f(x) - 1$ has degree at most $n-1$ and at least $n$ distinct roots, so $f(x) = 1$ everywhere, as desired. We wish to find the coefficient of $x^m$ in \[ \frac{n! x^n}{(1-x)(1-2x) \cdots (1-nx)}, \] which is the coefficient of $m-n$ in \[ \frac{1}{(\frac{1}{1} - x)(\frac{1}{2} - x) \cdots (\frac{1}{n} - x)}. \] Let $Q(x) = (x - \frac{1}{1})(x - \frac{1}{2}) \cdots (x - \frac{1}{n})$. Then for $1 \leq i \leq n$, we have \begin{align*} Q'(\frac{1}{i}) &= \prod_{1 \leq j \leq n, j \neq i} \left(\frac{1}{i} - \frac{1}{j} \right) \\ &= \frac{1}{i^{n-1}}\frac{1}{\frac{n!}{i}} \left( (-1)^{i-1} \prod_{j=1}^{i-1} (i-j) \right) \left( \prod_{j=i+1}^{n} (j-i) \right) \\ &= \frac{(i-1)! (n-i)!}{n!} \frac{(-1)^{i-1}}{i^{n-2}} \\ &= \frac{(-1)^{i-1} }{\binom{n}{i} i^{n-1}}. \end{align*} Hence, \begin{align*} [x^{m-n}] \left( \frac{1}{(\frac{1}{1} - x)(\frac{1}{2} - x) \cdots (\frac{1}{n} - x)} \right) &= [x^{m-n}] \left( (-1)^n \frac{1}{Q(x)} \right) \\ &= [x^{m-n}] \left (\sum_{i=1}^n \frac{(-1)^{n+i-1} \binom{n}{i} i^{n-1}}{x-\frac{1}{i}} \right) \\ &= \sum_{i=1}^n [x^{m-n}] \left(\frac{(-1)^{n-i} \binom{n}{i} i^{n}}{1-ix} \right) \\ &= \sum_{i=1}^n (-1)^{n-i} \binom{n}{i} i^{n+(m-n)} \\ &= {n \choose n} n^m - {n \choose n-1} (n-1)^m + \cdots + (-1)^{n-2} {n \choose 2} 2^m + (-1)^{n-1} {n \choose 1}, \end{align*} as desired.

I think Darij means c_i = 1 + sum_j=1^(i-1)(b_j + 1) not c_i = sum_j=1^(i-1)(b_j + 1) (sorry for my lack of LateX knowledge). Please correct me if I am wrong

We show that both numbers in the equation are equal to the number of surjections $[m] \to [n]$. It is clear that the RHS of the desired equation counts this by PIE. We show that the LHS counts this number in the following way. Let $f: [m] \to [n]$ be a surjection. Let $t_k$ be the smallest integer such that the restriction of $f$ to $[t_k]$ contains exactly $k$ elements in its range. It is clear that $t_1, \dots, t_n$ exist, are unique, and $t_1 < \dots < t_n$. For convenience, define $t_{n + 1} = m + 1$. From above, the integers $a_1 = t_2 - t_1, \dots, a_n = t_{n + 1} - t_n$ are all positive and sum to $m$ (note $t_1 = 1$). We claim that given the sequence $(a_1, \dots, a_n)$, there are $1^{a_1} \cdots n^{a_n}$ ways to construct $f$, which will solve the problem. Observe $f(1)$ has $n$ choices. $f(2), \dots, f(a_1)$ each have $1$ choice. $f(a_1 + 1)$ has $n - 1$ choices. $f(a_1 + 2), \dots, f(a_1 + a_2)$ each have $2$ choices. $\vdots$ $f(a_1 + \dots + a_{n - 1} + 1)$ has $1$ choice. $f(a_1 + \dots + a_{n - 1} + 2), \dots, f(a_1 + \dots + a_{n - 1} + a_n)$ each have $n$ choices. This gives $1^{a_1} \cdots n^{a_n}$ possibilities for $f$ as desired.

Similar to other generating functions in this thread, but posting for storage. The generating function of the left side is \begin{align*} \prod_{i = 1}^n\sum_{j = 1}^\infty (ix)^j. \end{align*}Applying the geometric series formula to each of the inner terms, this becomes \begin{align*} \frac{x^nn!}{(1 - x)(1 - 2x)\cdots(1 - nx)}. \end{align*} Now, we find the generating function of the right side. This is \begin{align*} \sum_{m \geq n}\left[\sum_{i = 1}^n (-1)^{n - i}\binom{n}{i}i^m\right]x^m &= \sum_{i = 1}^n(-1)^{n - i}\binom{n}{i}\sum_{m \geq n} (ix)^m \\ &= \sum_{i = 1}^n (-1)^{n - i}\binom{n}{i}\frac{(ix)^n}{1 - ix} \\ &= x^n\sum_{i = 1}^n \frac{(-1)^{n - i}\binom{n}{i}i^n}{1 - ix}, \end{align*}where the first equality is by swapping the order of summation, while the second is due to the geometric series formula. Hence, it suffices to check that \begin{align*} \frac{x^nn!}{(1 - x)(1 - 2x)\cdots(1 - nx)} &= x^n\sum_{i = 1}^n \frac{(-1)^{n - i}\binom{n}{i}i^n}{1 - ix} \\ \frac{n!}{(1 - x)(1 - 2x)\cdots(1 - nx)} &= \sum_{i = 1}^n \frac{(-1)^{n - i}\binom{n}{i}i^n}{1 - ix}. \end{align*}Upon multiplying through by $(1 - x)(1 - 2x)\cdots(1 - nx)$, this is equivalent to \begin{align} \sum_{i = 1}^n (-1)^{n - i}\binom{n}{i}i^n \cdot \frac{(1 - x)(1 - 2x)\cdots(1 - nx)}{1 - ix} &= n!. \end{align}Now, the left side is a polynomial of degree $n - 1$, while the right side is a polynomial of degree $0$. Hence, to check that they are the same polynomial, it suffices to check their equality for $n$ different values of $x$. We will show the equality when $x = \frac{1}{i}$, for $1 \leq i \leq n$. Indeed, when $x = \frac{1}{i}$, we have \begin{align*} \sum_{i = 1}^n (-1)^{n - i}\binom{n}{i}i^m \cdot \frac{(1 - x)(1 - 2x)\cdots(1 - nx)}{1 - ix} &= (-1)^{n - i}\binom{n}{i}i^n \cdot \frac{(i - 1)}{i}\cdots\frac{1}{i}\cdot\frac{(-1)}{i}\cdots\frac{-(n - i)}{i} \\ &= (-1)^{n - i}\binom{n}{i}i^n \cdot (-1)^{n - i} \frac{(i - 1)!(n - i)!}{i^{n - 1}} \\ &= \binom{n}{i}i\cdot (i - 1)!(n - i)! \\ &= n!. \end{align*}Therefore, as (1) holds for $n$ different values of $x$, it hold for all $x$. Thus, both sides of the given identity have the same generating function, implying that the identity is true, as desired. $\Box$

Observe that the left side is just asking for the $x^m$ coefficient of the generating function $$(x + x^2 + \cdots)(2x + 4x^2 + \cdots) \cdots (nx + n^2x^2 + \cdots),$$which simplifies to $$n!x^n \cdot \frac{1}{1 - x} \cdot \frac{1}{1 - 2x} \cdot \cdots \cdot \frac{1}{1 - nx}.$$We want to do a similar thing for the right hand side: we have the generating function $$\begin{aligned} \sum_{m \geq n} \left( \sum_{k = 1}^n (-1)^{n - k} \binom{n}{k} k^m \right) x^m &= \sum_{k = 1}^n (-1)^{n - k} \binom{n}{k} \sum_{m \geq n} k^mx^m \\ &= \sum_{k = 1}^n (-1)^{n - k} \binom{n}{k} \cdot \frac{k^nx^n}{1 - kx}, \end{aligned}$$which unfortunately does not simplify further. Thus we want to verify $$\sum_{k = 1}^n (-1)^{n - k} \binom{n}{k} \cdot \frac{k^n}{1 - kx} = n! \cdot \frac{1}{1 - x} \cdot \frac{1}{1 - 2x} \cdots \cdot \frac{1}{1 - nx},$$where we have divided out the $x^n$ from both sides. Now, we proceed with bashing Pascal's identity/binomial theorem for an hour and failing miserably. Then, we stop being dumb, and realize that we can turn this into a polynomial identity. The polynomial identity we get is $$\sum_{k = 1}^n (-1)^{n - k} \binom{n}{k} k^n (1 - x)(1 - 2x) \cdots (1 - (k - 1)x)(1 - (k + 1)x) \cdots (1 - nx) = n!.$$Observe that the RHS is actually a constant, so we can plug in "forbidden values" to check the identity. Let $x = \frac{1}{k}$. Then, the left hand side becomes $$(-1)^{n - k} \frac{n!}{k!(n - k)!} \cdot k^n \frac{k-1}{k} \cdot \frac{k-2}{k} \cdot \frac{1}{k} \cdot \frac{-1}{k} \cdots \frac{-(n - k)}{k},$$since we get a ton of cancellation for the other terms in the summation. Now, it is easy to verify that this is equal to $n!$.

Both sides count the number of ways to color the first $m$ natural numbers with $n$ colors, such that each color is used at least once. The RHS equivalence can be established by a simple PIE argument, so we will focus on the LHS. First, we choose an order of appearance of all colors in $n!$ ways. Also, for the sake of convenience, suppose that $m+1$ has the fixed color void distinct from all existing hues. Suppose that we walk from the start of the "number segment" $[1,m+1]$ to the end, taking steps of length $1$, and the $i+1$th new color appears $a_{i}$ steps after the $i$th new color appears for all positive integers $i\le n$. There are $i^{a_{i}-1}$ ways to pick available colors for the cubes strictly between the first appearance of the $i$th new color and the first appearance of the $i+1$th new color, and multiplying everything together does the trick.

\begin{align*} \sum_{m\geq 1} \sum_S 1^{a_1} 2^{a_2} \cdots n^{a_n} X^m &=\sum_{a_n\geq 1} \sum_{a_2\geq 2} \cdots \sum_{a_1\geq 1} 1^{a_1} 2^{a_2} \cdots n^{a_n}X^{a_1+a_2+\cdots +a_n} \\ &= \sum_{a_n\geq 1} (nX)^{a_n}\sum_{a_{n-1}\geq 1}((n-1)X)^{a_{n-1}} \cdots \sum_{a_1\geq 1} X^{a_1} \\ &= \frac{X}{1-X} \frac{2X}{1-2X} \cdots \frac{nX}{1-nX} \\ &=\frac{n! X^n}{(1-X)(1-2X) \cdots (1-nX)} \end{align*}Let this sum be $S_1$. \begin{align*} \sum_{m \geq n}\left(\sum_{k = 1}^n (-1)^{n - k}\binom{n}{k}k^m\right)X^m &= \sum_{k = 1}^n (-1)^{n - k}\binom{n}{k}\frac{(kX)^n}{1 - kx} \\ &= \left(\sum_{k = 1}^n \frac{(-1)^{n - k}\binom{n}{k}k^n}{1 - kX} \right)X^n \\ &= \left(\frac{\sum_{k\geq 1} (-1)^{n-k}\binom{n}{k}k^n \prod_{i\neq k}(1-iX)}{\prod_{j=1}^{n} (1-jX)} \right) \end{align*}Let this sum be $S_2$. In order to prove that $S_1=S_2$, we are left to show that $$n! = \sum_{k\geq 1} (-1)^{n-k}\binom{n}{k}k^n \prod_{i\neq k}(1-iX)$$Consider the polynomial $$P(X)=\sum_{k\geq 1} (-1)^{n-k}\binom{n}{k}k^n \prod_{i\neq k}(1-iX) -n!$$It is obvious that $$0=P(1)=P(\frac{1}{2})=\cdots =P(\frac{1}{n})$$but $deg P \leq n-1 \Rightarrow P(X)=0$, and the problem is now finished.

It turns out both sides are counting the number of ways to place the numbers $1,\ldots,m$ into $n$ distinguishable boxes such that no box is empty. The RHS counts this based on PIE, so we just have to prove that the LHS equals this too. Since the boxes are distinguishable and nonempty (thus all distinct in terms of contents), it suffices to show that there are $$\sum_{b_1+\cdots+b_n=m-n} 1^{b_1}2^{b_2}\cdots n^{b_n}$$ways to place the numbers, where $b_i \geq 0$, where the order of boxes doesn't matter. WLOG, label the boxes $1,\ldots,n$, such that $1=M_1<\cdots<M_n$ are the smallest numbers in boxes $1,\ldots,n$ respectively—essentially, we fix the order of the boxes. Then for some choice of $(M_1,\ldots,M_n)$, we let $b_i=M_{i+1}-M_i-1$, where we define $M_{n+1}=m$. Then we clearly have $b_1+\cdots+b_n=m-n$. Further: There is one position where $M_1,\ldots,M_n$ can go For some $x \in (M_i,M_{i+1})$ for $1 \leq i \leq n$, there are $i$ boxes ($1,\ldots,i$) where $x$ can be placed Since there are $M_{i+1}-M_i-1=b_i$ integers in the interval $(M_i,M_{i+1})$, it follows that there are $1^{b_1}2^{b_2}\cdots n^{b_n}$ ways to place the numbers once we have chosen $(M_1,\ldots,M_n)$. Summing over all $(M_1,\ldots,M_n)$, which corresponds to summing over all $(b_1,\ldots,b_n)$, we arrive at the desired conclusion. $\blacksquare$

We will prove the following obviously equivalent statement: \[\sum_{\substack{a_1 + \dots + a_n = m \\ a_i \ge 0}} 1^{a_1} 2^{a_2} 3^{a_3} \cdots n^{a_n} = \frac{1}{n!}\sum_{k=1}^n (-1)^{n-k} \binom nk k^{m+n}.\]To do this, we will induct on $n$. Base case $n=1$ is trivial, so suppose that $n-1$ works and we will prove that $n$ works. Indeed, we have \begin{align*} & \sum_{\substack{a_1 + \dots + a_n = m \\ a_i \ge 0}} 1^{a_1} 2^{a_2} 3^{a_3} \cdots n^{a_n} \\ =& \sum_{s=0}^{m}\left(\sum_{\substack{a_1 + \dots + a_{n-1} = s \\ a_i \ge 0}} 1^{a_1} 2^{a_2} 3^{a_3} \cdots (n-1)^{a_{n-1}}\right)n^{m-s} \\ =& \sum_{s=0}^{m}\frac{1}{(n-1)!}\sum_{k=1}^n (-1)^{n-1-k}\binom{n-1}{k} k^{s+n-1}\cdot n^{m-s} \\ =& \sum_{k=1}^n \frac{1}{(n-1)!}(-1)^{n-1-k}\binom{n-1}{k} k^{n-1} n^m \sum_{s=0}^{m}\left(\frac kn\right)^s \\ =& \sum_{k=1}^n \frac{n}{n!}(-1)^{n-1-k}\cdot\frac{n-k}{n}\binom{n}{k} k^{n-1} n^m\cdot\frac{1-(k/n)^{m+1}}{1-k/n} \\ =& \frac{1}{n!}\sum_{k=1}^n (-1)^{n-1-k}\cdot\binom{n}{k} k^{n-1} n^{m+1}\cdot\left(1-(k/n)^{m+1}\right) \\ =& \frac{1}{n!}\sum_{k=1}^n (-1)^{n-k}\binom{n}{k} k^{n-1}\left(k^{m+1}-n^{m+1}\right). \end{align*}Thus it suffices to show that \[ \sum_{k=1}^{n}(-1)^{n-k}\binom nk k^{n-1}=0. \]Let $P(x)=(x-1)^n$. Then define the awa operation be a function that takes a polynomial $f(x)$ and returns $xf'(x)$. It is easy to see that if $f(x)=a_0+a_1 x+a_2 x^2+\dots$ then $xf'(x)=0a_0+1a_1 x+2a_2 x^2+\dots$ If $Q(x)$ is the result of applying the awa operation on $P(x)$ $n-1$ times, then clearly $Q(1)$ is equal to the sum that we want to show is zero. However, since the multiplicity of $1$ as a root in $P(x)$ is $n$, the multiplicity of $1$ as a root in $Q(x)$ is at least $1$, i.e. $Q(1)=0$, as desired. $\blacksquare$

$ $

Needed a hint for the second part, since it is kinda tricky.

Let $f(n,m)$ denote the sum on the left hand side. The main claim is the following. Claim: We have the following recurrence: $$f(n,m)=n[f(n,m-1)+f(n-1,m-1)].$$ When $a_n=1$, the total contribution is $nf(n-1,m-1)$ since we have a multiplier of $n$ and $a_1\dots+a_{m-1}=n-1$. Otherwise if $a_n\geq 2$, we can "give" one to $a_n$, multiplying the value by $n$, and still have $m-1$ left to distribute among $n$ variables, thus contributing $nf(n,m-1)$. Clearly $f(n,m)=0$ for $m<n$, and $f(1,m)=1$. We will now use induction. We will show that $(n,m-1)$ and $(n-1,m-1)$ working implies that $(n,m)$ works. Assume that $$f(n,m-1)=\sum_{k=1}^n (-1)^{n-k} {n\choose k}k^{m-1}$$and $$f(n-1,m-1)=\sum_{k=1}^{n-1} (-1)^{n-1-k} {n-1\choose k}k^{m-1}.$$ It suffices to show that $$n \left [ \sum_{k=1}^n (-1)^{n-k} {n\choose k}k^{m-1}+\sum_{k=1}^{n-1} (-1)^{n-1-k} {n-1\choose k}k^{m-1}\right ] =\sum_{k=1}^{n} (-1)^{n-k} {n\choose k}k^{m}.$$ On the LHS, the $k=n$ term of the fist sum multiplied by $n$ cancels with the $k=n$ term of the right hand sum, so this simplifies to $$n\sum_{k=1}^{n-1}(-1)^{n-k}{n-1\choose k-1}k^{m-1}=\sum_{k=1}^{n-1}(-1)^{n-k} {n\choose k}k^{m}$$(here the LHS was factored and the fact that ${n\choose k}-{n-1\choose k}={n-1\choose k-1}$ was used. However, since $$n{n-1\choose k-1}k^{m-1}={n\choose k}k^{m}\iff n{n-1\choose k-1}=k{n\choose k},$$the two sums are actually term-wise equal, which shows the claim. Now, to complete the base case, it suffices to show that the RHS is zero when $m<n$. However, this follows by taking the $n$th order finite differences of the sequence $k^m$, so we are does.

This is a problem from the book《Enumerative Combinatorics, Vol. 1》by Richard P. Stanley. See exercise $45$ in Chapter $1$.

Let $m, n \in \mathbb{N}^*$ with $m \geq n$, and define $$ S=\left\{ x=( a_1, a_2, \ldots, a_n) \mid a_i \in \mathbb{N}^*,\sum_{i=1}^n a_i=m \right\}. $$Prove that $$ \sum_{x=( a_1, a_2, \ldots, a_n) \in S} 1^{a_1} 2^{a_2} \cdots n^{a_n} = \binom{n}{n} n^m - \binom{n}{n-1} (n-1)^m + \cdots + (-1)^{n-2} \binom{n}{2} 2^m + (-1)^{n-1} \binom{n}{1}. $$ Fix $n$, and for each $ m \in \mathbb{N}^* $, let $ b_m=\sum_{x=( a_1, a_2, \ldots, a_n) \in S} 1^{a_1} 2^{a_2} \cdots n^{a_n} $. For convenience, define $ b_0=0 $ and let $ \mathcal{B} $ be the ordinary generating function for the sequence $ \{b_m\} $. Given the conditions, we have $$ \mathcal{B}(X)=\left(\sum_{k=1}^{\infty} X^k \right) \cdot \left( \sum_{k=1}^{\infty} (2X)^k \right) \cdots \left(\sum_{k=1}^{\infty} (nX)^k \right) = \frac{n! X^n}{(1 - X)(1 - 2X) \cdots (1 - nX)}. $$According to https://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html $$ \mathcal{B}(X) = n! \cdot \mathcal{S}_n(X), $$where $ \mathcal{S}_n(X) $ is the ordinary generating function for the Stirling numbers of the second kind, $ \left\{ m \brace n \right\}_{m=0}^{\infty} $. The problem will be solved if we can demonstrate that $$ n! \cdot {m \brace n} = \binom{n}{n} n^m - \binom{n}{n-1} (n-1)^m + \cdots + (-1)^{n-2} \binom{n}{2} 2^m + (-1)^{n-1} \binom{n}{1}. $$Consider the sets $ A = [m] $ and $ B = [n] $, and let $ \mathcal{F} $ denote the set of surjective functions $ f: A \to B $. We will count $ |\mathcal{F}| $ in two ways. 1. Each surjective function $ f \in \mathcal{F} $ can be constructed as follows: a. Partition $ A $ into $ n $ subsets. There are $ {m \brace n} $ ways to do this. b. Establish a bijection between the $ n $ subsets and the elements of $ B $, which can be done in $ n! $ ways. Each sequence of choices uniquely determines a surjective function $ f: A \to B $, giving us $$ |\mathcal{F}| = n! {m \brace n}. $$2. For each $ i \in [n] $, let $ X_i = \{ \text{functions } f: A \to B \mid i \not \in f(A) \} $. Then, the total count of surjections is $$ |\mathcal{F}| = n^m - \left| \bigcup_{i=1}^n X_i \right|. $$Observing that: 1. For each $ i \in [n] $, $ |X_i| = (n-1)^m $. 2. For each $ 1 \leq i_1 < i_2 < \cdots < i_l \leq n $, $$ \left| X_{i_1} \cap X_{i_2} \cap \cdots \cap X_{i_l} \right| = (n - l)^m. $$By the inclusion-exclusion principle, we have $$ |\mathcal{F}| = \binom{n}{n} n^m - \binom{n}{n-1} (n-1)^m + \cdots + (-1)^{n-2} \binom{n}{2} 2^m + (-1)^{n-1} \binom{n}{1}. $$This completes the proof.

Spacesam wrote: Observe that the left side is just asking for the $x^m$ coefficient of the generating function $$(x + x^2 + \cdots)(2x + 4x^2 + \cdots) \cdots (nx + n^2x^2 + \cdots),$$which simplifies to $$n!x^n \cdot \frac{1}{1 - x} \cdot \frac{1}{1 - 2x} \cdot \cdots \cdot \frac{1}{1 - nx}.$$We want to do a similar thing for the right hand side: we have the generating function $$\begin{aligned} \sum_{m \geq n} \left( \sum_{k = 1}^n (-1)^{n - k} \binom{n}{k} k^m \right) x^m &= \sum_{k = 1}^n (-1)^{n - k} \binom{n}{k} \sum_{m \geq n} k^mx^m \\ &= \sum_{k = 1}^n (-1)^{n - k} \binom{n}{k} \cdot \frac{k^nx^n}{1 - kx}, \end{aligned}$$which unfortunately does not simplify further. Thus we want to verify $$\sum_{k = 1}^n (-1)^{n - k} \binom{n}{k} \cdot \frac{k^n}{1 - kx} = n! \cdot \frac{1}{1 - x} \cdot \frac{1}{1 - 2x} \cdots \cdot \frac{1}{1 - nx},$$where we have divided out the $x^n$ from both sides. Now, we proceed with bashing Pascal's identity/binomial theorem for an hour and failing miserably. Then, we stop being dumb, and realize that we can turn this into a polynomial identity. The polynomial identity we get is $$\sum_{k = 1}^n (-1)^{n - k} \binom{n}{k} k^n (1 - x)(1 - 2x) \cdots (1 - (k - 1)x)(1 - (k + 1)x) \cdots (1 - nx) = n!.$$Observe that the RHS is actually a constant, so we can plug in "forbidden values" to check the identity. Let $x = \frac{1}{k}$. Then, the left hand side becomes $$(-1)^{n - k} \frac{n!}{k!(n - k)!} \cdot k^n \frac{k-1}{k} \cdot \frac{k-2}{k} \cdot \frac{1}{k} \cdot \frac{-1}{k} \cdots \frac{-(n - k)}{k},$$since we get a ton of cancellation for the other terms in the summation. Now, it is easy to verify that this is equal to $n!$. The thing is, does m >= 0 instead of m >= n for the right hand side work? Why?