Evaluating $\sum_{i=0}^k \frac{(-1)^{k-i}k! (n+i)^{k-1}}{i!(k-i)!}$ How to evaluate the the following sum where $n $ is an integer greater than $0$.
$$\sum_{i=0}^k \frac{(-1)^{k-i}k! (n+i)^{k-1}}{i!(k-i)!}$$
I think the answer is $0$, but I can not prove it.
 A: The statement is true, one way to see it is to define a operator $L$ on the spaces of real sequences indexed by $\mathbb{N}$ by:
$$a = (a_k)_{k\in\mathbb{N}} \quad\mapsto\quad L(a)_k = a_{k+1},\;k \in \mathbb{N} $$
i.e. shift the index of the sequence $a$ to the left by one unit. In terms of $L$, the inequality can be formally rewritten as
$$
\sum_{i=0}^k (-1)^{k-i} \binom{k}{i} (n+i)^{k-1} =
\sum_{i=0}^k (-1)^{k-i} \binom{k}{i} L^i(n^{k-1}) = (L - 1)^k(n^{k-1}) = 0$$
This is equivalent to claiming: 

Given $n^{k-1}$, a polynomial in $n$ of degree $k-1$, the $k^{th}$ time finite difference of it vanishes.

To prove the statement, it just suffices to observe for any polynomial $P(n)$ of degree $m$,
the finite difference of $P(n)$, $P(n+1) - P(n)$, is a polynomial of degree $m-1$.
A: Let
$$
P_k(z):=\sum_{i=0}^k\frac{(-1)^{k-i}k!(z+i)^{k-1}}{i!(k-i)!}=(-1)^k\sum_{i=0}^k(-1)^i{k\choose i}(z+i)^{k-1}=(-1)^kQ_k(z),
$$
where
$$
Q_k(z)=\sum_{i=0}^k(-1)^i{k\choose i}(z+i)^{k-1}.
$$
Obviously 
$$
Q_1(z)=1-1=0 \quad \forall z
$$ 
For $k \ge 2$ we have
\begin{eqnarray}
Q_k(z)&=&z^{k-1}+(-1)^k(z+k)^{k-1}+\sum_{i=1}^{k-1}(-1)^i{k\choose i}(z+i)^{k-1}\\
&=&z^{k-1}+(-1)^k(z+k)^{k-1}+\sum_{i=1}^{k-1}(-1)^i\left[{k-1\choose i}+{k-1\choose i-1}\right](z+i)^{k-1}\\
&=&z^{k-1}+\sum_{i=1}^{k-1}(-1)^i{k-1\choose i}(z+i)^{k-1}+\sum_{i=1}^{k-1}(-1)^i{k-1\choose i-1}(z+i)^{k-1}+(-1)^k(z+k)^{k-1}\\
&=&\sum_{i=0}^{k-1}(-1)^i{k-1\choose i}(z+i)^{k-1}+\sum_{i=1}^k(-1)^i{k-1\choose i-1}(z+i)^{k-1}\\
&=&Q_{k-1}(z)-\sum_{i=0}^{k-1}(-1)^i{k-1\choose i}(z+1+i)^{k-1}\\
&=&Q_{k-1}(z)-Q_{k-1}(z+1).
\end{eqnarray}
Since $Q_1(z)=0$ for every $z$, it follows by induction that
$$
Q_k(z)=Q_{k-1}(z)-Q_{k-1}(z+1)=0 \quad \forall k \ge 2, \forall z.
$$
Thus for every $z$ we have
$$
P_k(z)=0 \quad \forall k \ge 1.
$$
A: This can be shown using the identities
$$
\begin{align}
\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}\binom{k}{m}
&=\left\{\begin{array}{}
0&\text{if }n\ne m\\
1&\text{if }n=m
\end{array}\right.\\[6pt]
&=[n=m]\tag{1}
\end{align}
$$
where $[\dots]$ are Iverson Brackets and
$$
\sum_{k=0}^m\binom{n}{k}\,\begin{Bmatrix}m\\k\end{Bmatrix}k!=n^m\tag{2}
$$
where $\begin{Bmatrix}n\\k\end{Bmatrix}$ is a Stirling number of the second kind. This may look daunting because of the Stirling numbers, but all that $(2)$ really says is that $x^m$ can be written as a linear combination of binomial polynomials $\displaystyle\binom{x}{k}$ of degree $k\le m$.
Then, using $(1)$ and $(2)$, we have for $m\lt n$
$$
\begin{align}
\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}(x+k)^m
&=\sum_{k=0}^n\sum_{j=0}^m(-1)^{n-k}\binom{n}{k}\binom{m}{j}x^{m-j}k^j\\
&=\sum_{k=0}^n\sum_{j=0}^m\sum_{i=0}^j(-1)^{n-k}\binom{n}{k}\binom{m}{j}x^{m-j}\binom{k}{i}\begin{Bmatrix}j\\i\end{Bmatrix}i!\\
&=\sum_{j=0}^m\sum_{i=0}^j\binom{m}{j}x^{m-j}\,[n=i]\,\begin{Bmatrix}j\\i\end{Bmatrix}i!\\
&=\sum_{j=0}^m\binom{m}{j}x^{m-j}\begin{Bmatrix}j\\n\end{Bmatrix}n!\\
&=0
\end{align}
$$
since $\displaystyle\binom{m}{j}\begin{Bmatrix}j\\n\end{Bmatrix}=0$ if $m\lt n$.
