Proving a closed form of $\sum_{j=0}^m\binom{m}{j}(-1)^{m-j}j^k$ (for $0\leq k\le m$). I'm attempting to show that, given a positive integer $m$ and a non-zero constant $\lambda,$ the sequence $n\mapsto\lambda^nn^k$ satisfies the recurrence relation $$\sum_{j=0}^m\binom{m}{j}(-\lambda)^{m-j}a_{n+j}=0$$ for any integer $0\le k<m.$ I have reduced the problem to showing that $$\sum_{j=0}^m\binom{m}{j}(-1)^{m-j}j^k=0$$ for such $k.$ To prove the $k=0$ case, one need only apply the binomial theorem to $(1-1)^m,$ but I'm stymied trying to prove it for other such $k.$
I checked several examples specifically to make sure I hadn't erred along the way, and it seems that it's true. I also determined (quite by accident) the apparent identity $$\sum_{j=0}^m\binom{m}{j}(-1)^{m-j}j^m=m!,$$ which I have no idea how to prove, either. This leads me to wonder how one could possibly go about determining a closed form for $f(k,m):=\sum_{j=0}^m\binom{m}{j}(-1)^{m-j}j^k.$
Any suggestions/hints (for finding a closed form, proving the identities, or proving the recurrence relation is satisfied) would be appreciated.
 A: This is (almost) the formula for the Stirling numbers of the second kind which count the partitions of $\{1,\dots,n\}$ into non-empty sets.
They have the generating function
$$ \sum_{n,m} \begin{Bmatrix} n \\ m \end{Bmatrix} \frac{x^n}{n!}y^m = \exp(y(e^x - 1)). $$
Then
\begin{align}
\begin{Bmatrix} n \\ m \end{Bmatrix} &= \left[ \frac{x^n}{n!}y^m \right] \exp(y(e^x - 1)) \\
&= \frac{1}{m!} \left[ \frac{x^n}{n!} \right] (e^x - 1)^m \\
&= \frac{1}{m!} \left[ \frac{x^n}{n!} \right] \sum_{j = 0}^m \binom{m}{j}e^{jx}(-1)^{m - j} \\
&= \frac{1}{m!} \sum_{j = 0}^m \binom{m}{j}j^n(-1)^{m - j}.
\end{align}
So one has
$$ \sum_{j = 0}^m \binom{m}{j}j^n(-1)^{m - j} = m! \begin{Bmatrix} n \\ m \end{Bmatrix}. $$
The right hand side evaluates to $0$ when $n < m$ and to $m!$ when $n = m$.
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
\sum_{j = 0}^{m}{m \choose j}(-1)^{m - j}\,j^{k} & =
\pars{-1}^{m}\sum_{j = 0}^{m}{m \choose j}(-1)^{\,j}
\,\braces{k!\bracks{z^{k}}\expo{\,jz}}
\\[5mm] & =
\pars{-1}^{m}\,k!\bracks{z^{k}}\sum_{j = 0}^{m}{m \choose j}(-\expo{z})^{\,j} =
\pars{-1}^{m}\,k!\bracks{z^{k}}\bracks{1 + \pars{-\expo{z}}}^{m}
\\[5mm] & =
k!\bracks{z^{k}}\pars{\expo{z} - 1}^{m} =
k!\bracks{z^{k}}\bracks{m!\sum_{n = 0}^{\infty}{n \brace m}{z^{n} \over n!}}
\end{align}

$\ds{{n \brace m}}$ is a
  Stirling Number of the Second Kind.

Then,
\begin{align}
\sum_{j = 0}^{m}{m \choose j}(-1)^{m - j}\,j^{k} & =
k!\,m!{k \brace m}\,{1 \over k!} = \bbx{m!{k \brace m}}
\end{align}
A: Recall that $[m]=\{1,2,\cdots ,m\}$ and $A^B=\{f:A\longrightarrow B:\text{ f function}\}$.>By inclusion exclusion:
$$\sum_{j=0}^m \binom{m}{j}(-1)^j(m-j)^m=m^m-\sum_{j=1}^m \binom{m}{j}(-1)^{j-1}(m-j)^m=|[m]^{[m]}\setminus \bigcup _{j=1}^m A_j\|,$$
such that $A_x=\{f\in [m]^{[m]}:x\not \in Im(f)\}$ so $|A_x|=(m-1)^m$ and if $x\neq y,$ $A_x\cap A_y=(m-2)^m$ and so on. But that set is nothing more than permutations because are functions from $[m]$ to $m$ that are surjective. And there are $m!$ of them.
A: You don't need to know any combinatorics to solve your original problem, just linear algebra (which happens to have combinatorial consequences). Let $S$ denote the (forward) shift operator, which sends a sequence $a_n$ to the sequence
$$(Sa)_n = a_{n+1}.$$
Saying that a sequence satisfies a linear recurrence $a_{n+k} = c_{k-1} a_{n+k-1} + \dots + c_0 a_n$ is equivalent to saying that it satisfies
$$(S^k - c_{k-1} S^{k-1} - \dots - c_0) a = 0.$$
Here are some simple observations:


*

*$a_n = r^n$ satisfies $(S - r) a = 0$.

*$(S - 1)$ computes the forward difference $(\Delta a)_n = a_{n+1} - a_n$. The forward difference of a polynomial of degree $d$ is a polynomial of degree $d-1$, so it follows that $a_n = n^d$ satisfies $(S - 1)^{d+1} a = 0$.

*If $a_n = n^k r^n$ then 


$$\boxed{ (S - r) a = (n + 1)^k r^{n+1} - n^k r^{n+1} = (\Delta n^k) r^{n+1} }.$$
This is the key computation. Induction gives
$$(S - r)^i a = (\Delta^i n^k) r^{n+i}$$
and hence
$$(S - r)^m a = 0, m \ge k + 1.$$
In fact it's possible to reformulate the entire theory of linear recurrences in terms of the shift operator; basically the point is that you can factor $S^k - c_{k-1} S^{k-1} - \dots$ into irreducible factors, as a polynomial in $S$. 
The Stirling numbers appear implicitly in this computation as the value of $\Delta^i n^k$ at $0$. Here are some other notes regarding the patterns that have been described in this discussion so far:


*$$\Delta^i a = (S - 1)^i a = \sum_{j=0}^i (-1)^{i-j} {i \choose j} S^j a$$

*If $a_n = c_d n^d + \dots$ is a polynomial of degree $d$ with leading coefficient $c_d$, then $(\Delta a)_n = d c_d n^{d-1} + \dots$ is a polynomial of degree $d-1$ with leading coefficient $dc_d$.

*Inducting on 5 gives $(\Delta^d n^d) = d!$. 

