Binomial Sum: Values I need this as lemma.
Regard the sums:
$$S_k:=\sum_{n=0}^N\binom{N}{n}(-1)^{N-n}n^k\quad(k\in\mathbb{N}_0)$$
Then it holds:
$$S_k\stackrel{k<N}{=}0\quad S_k\stackrel{k=N}{=}N!$$
How can I check this?
 A: We have by binomial theorem $$\left(x-1\right)^{N}=\sum_{n=0}^{N}\dbinom{N}{n}x^{n}\left(-1\right)^{N-n}
 $$ now if you take the derivative we have $$N\left(x-1\right)^{N-1}=\sum_{n=0}^{N}\dbinom{N}{n}nx^{n-1}\left(-1\right)^{N-n}
 $$ hence $$Nx\left(x-1\right)^{N-1}=\sum_{n=0}^{N}\dbinom{N}{n}nx^{n}\left(-1\right)^{N-n}
 $$ and if we take the derivative again $$N\left(x-1\right)^{N-1}+N\left(N-1\right)x\left(x-1\right)^{N-2}=\sum_{n=0}^{N}\dbinom{N}{n}n^{2}x^{n-1}\left(-1\right)^{N-n}
 $$ hence $$Nx\left(x-1\right)^{N-1}+N\left(N-1\right)x^{2}\left(x-1\right)^{N-2}=\sum_{n=0}^{N}\dbinom{N}{n}n^{2}x^{n}\left(-1\right)^{N-n}
 $$ then if you derive at most $N-1
 $ times on the LHS there is a sum in which in every terms there is a power of $\left(x-1\right)
 $. So if we take $x=1
 $ we have $$0=\sum_{n=0}^{N}\dbinom{N}{n}n^{k}\left(-1\right)^{N-n}.
 $$
 Addendum. About your new request, note that if you differentiate $N
 $ times we get, using the same arguments as before$$ \textrm{terms with powers of}\left(x-1\right)+N!x^{N}=\sum_{n=0}^{N}\dbinom{N}{n}n^{N}x^{n}\left(-1\right)^{N-n}
 $$ and so again with $x=1
 $ we get $$N!=\sum_{n=0}^{N}\dbinom{N}{n}n^{N}\left(-1\right)^{N-n}.
 $$
A: Count surjective functions $[k]\to [N]$! (There are none, yes!)
To expand a bit, let us take $k,N$ arbitrary and count non-surjective functions $f:[k]\to [N]$. Now let $A_j$ be the set of functions that miss $j\in N$. Then this set has cardinality equal to that of the set of functions $[k]\to [N-1]$ and more generally if $j_1<\cdots <j_r$ then $A_{j_1}\cap\cdots\cap A_{j_r}$ has cardinality equal to that of the set of functions $[k]\to [N-r]$, that is $(N-r)^k$. By inclusion exclusion we get that $$\left\lvert \bigcap_{j=1}^N A_j\right\rvert =\sum_{j_1<\cdots <j_r} (-1)^{r-1}\lvert A_{j_1}\cdots A_{j_r}\lvert\\=-\sum_{r=1}^{N} (-1)^r \binom{N}{r}(N-r)^k$$
The number of surjective functions is the complement of this against the cardinality $N^k$ of all functions $[k]\to [N]$ which gives the result $$\# \text{surjective functions } [k]\to [N]=\sum_{r=0}^N (-1)^{r}\binom Nr (N-r)^k$$
A: Consider the function
$y = x^k$.
For any polynomial,
its first difference
has degree one smaller than it.
This follows from
$(x+1)^k-x^k
=kx^{k-1}+$ (smaller order terms).
By induction,
the $m$-th difference of a polynomial
of degree $d$,
where $m \le d$,
has degree $d-m$.
Therefore,
the $d$-th difference of
a polynomial of degree $d$
is constant,
so the
$d+1^{st}$ difference of a
polynomial of degree $d$ is zero.
The above expression
is the N-th difference of
$x^k$,
where $N> k$.
Therefore it is zero.
A: Since $k!\binom{x}{k}$ is a degree $k$ polynomial in $x$ with lead coefficient $1$ it is pretty easy see that it is possible to write
$\newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}}$
$$
x^k=\sum_{j=0}^kj!\stirtwo{k}{j}\binom{x}{j}\tag{1}
$$
where $\stirtwo{k}{k}=1$. The numbers $\stirtwo{k}{j}$ are the Stirling Numbers of the Second Kind.
Using $(1)$, we get
$$
\begin{align}
\sum_{n=0}^N\binom{N}{n}(-1)^{N-n}n^k
&=\sum_{n=0}^N\binom{N}{n}(-1)^{N-n}\sum_{j=0}^kj!\stirtwo{k}{j}\binom{n}{j}\\
&=\sum_{j=0}^k\sum_{n=j}^N(-1)^{N-n}j!\stirtwo{k}{j}\binom{N}{n}\binom{n}{j}\\
&=\sum_{j=0}^k\sum_{n=j}^N(-1)^{N-n}j!\stirtwo{k}{j}\binom{N}{j}\binom{N-j}{n-j}\\
&=\sum_{j=0}^kj!\stirtwo{k}{j}\color{#C00000}{\binom{N}{j}}\color{#00A000}{\sum_{n=0}^{N-j}(-1)^{N-j-n}\binom{N-j}{n}}\\
&=\sum_{j=0}^kj!\stirtwo{k}{j}\color{#C00000}{\binom{N}{j}}\color{#00A000}{0^{N-j}}\\
&=N!\stirtwo{k}{N}\tag{2}
\end{align}
$$
If $k\lt N$, then, since $j\le k$, all the terms in the sum from the second to the last line of $(2)$ are $0$. Furthermore, $\stirtwo{k}{N}=0$ for $k\lt N$.
If $k=N$, then, since $\stirtwo{k}{k}=1$, the sum is $N!$.
Note that in the last two sums of $(2)$, if $N\lt j$, $\binom{N}{j}=0$ and if $N\gt j$, $0^{N-j}=0$. It is only if $N=j$ that $\binom{N}{j}0^{N-j}=1$.
