For n $\geq$ k, what is $\sum_{i=1}^n (-1)^i {n \choose i} i^k$? For $n \geq k$, what is $\sum_{i=1}^n (-1)^i {n \choose i} i^k$ where $n,k$ are positive integers?
I think that this expression equals $0$ when $n>k$ and $(-1)^n n!$ when $n=k$, through checking the simpler cases, but I am not sure how to prove that this is true.
I tried using binomial theorem, but I don't think it applies in this case, since we are multiplying by the $i^k$ inside the sum. I'm guessing that it has to do with the inclusion-exclusion principle, but I'm not sure how to apply it in this case.
 A: $(-1)^n$ times this is the number of onto maps $$\{1,2,\dots,k\}\to \{1,2,\dots,n\}$$
You get that by an inclusion-exclusion argument.
You are correct: When $k=n,$ it is $(-1)^nn!$, and it is zero when $k<n.$ In general, we can express your sum in terms of the Stirling numbers of the second kind. Namely,
$$
\sum_{k=0}^n (-1)^i\binom{n}i i^k=(-1)^nn! {k \brace n}
$$
where ${k\brace n}$ is the number of ways to partition $\{1,\dots,k\}$ into $n$ unlabeled sets. The connection with maps $\{1,\dots,k\}\to \{1,\dots,n\}$ should be clear; to choose such a map, you partition the domain into $k$ parts in ${k\brace n}$ ways, and then bijectively map the parts to the codomain in $n!$ ways.

The inclusion-exclusion
Let $[m]=\{1,\dots,m\}.$ Define:
$$A=\{f:[k]\to [n]\}.$$
Let $$A_i=\{f\in A\mid \forall j\in [k](f(j)\neq i)\}\quad i\in [n]$$
So $A_i$ are the functions which do not have $i$ in the range.
Then inclusion-exclusion gives $$A\setminus(A_1\cup\cdots \cup A_n)|=\sum_{j=0}^n(-1)^{j}\binom nj (n-j)^k.$$
When $k>0,$ at least, we can ignore the term $j=n,$ since $(n-n)^k=0.$
Letting $i=n-j$ this becomes:
$$\sum_{i=1}^{n} (-1)^{n-i}\binom n{n-i}i^k$$
But $(-1)^{n-i}=(-1)^n(-1)^i,$ and $\binom n{n-i}=\binom ni,$ so we get:
$$(-1)^n\sum_{i=1}^n(-1)^i\binom ni i^k$$
Which is $(-1)^n$ times your formula.
But the set $A\setminus(A_1\cup\cdots\cup A_n)$ is all onto maps $[k]\to [n].$
When $k=0,$ you need to include the value $i=0$ in the sum, using the combinatorial definition $0^0=1.$
