<s>[INST] how to prove this combinatorial identity I accidentally find? Today when I solve a counting problem using different methods I find the following (seemingly correct) combinatorial identity, but I can't find it on the Internet and I can't prove its correctness neither. But I have verified its correctness with positive integer $n$ within $[0, 1000]$ using a simple computer program. Anyone can give a proof to this identity (or any link to its proof)?
$$\frac{(n+1)n}{2} \cdot n! = \sum\limits_{k=0}^{n} (-1)^k \cdot \frac{n!}{k!\cdot(n-k)!} \cdot (n-k)^{n+1}$$
And equivalently if you want,
$$\frac{(n+1)n}{2} = \sum\limits_{k=0}^{n} (-1)^k \cdot \frac{1}{k!\cdot(n-k)!} \cdot (n-k)^{n+1}$$
 [/INST] Another way is to consider that the backward finite difference (backward Delta) is defined as
$$
\nabla _x \,f(x) = f(x) - f(x - 1)
$$
and we have that its $n$-th iteration is:
$$
\nabla _x ^n \,f(x) = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^k \left( \begin{gathered}
  n \\ 
  k \\ 
\end{gathered}  \right)\;f(x - k)} 
$$
therefore the RHS is:
$$
\sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^k \left( \begin{gathered}
  n \\ 
  k \\ 
\end{gathered}  \right)\;\left( {n - k} \right)^{n + 1} }  = \left. {\nabla _x ^n \,x^{n + 1} } \right|_{\,x = n} 
$$
Now $x^{\,n + 1} $ is a polynomial of degree $n+1$ and we can express it in terms
of the Stirling Numbers of $2$nd kind and Falling Factorials of $x$ as
$$
x^{\,n + 1}  = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left\{ \begin{gathered}
  n + 1 \\ 
  k \\ 
\end{gathered}  \right\}\;x^{\,\underline {\,k\;} } } 
$$
The backward Delta of the falling factorial is given by:
$$
\begin{gathered}
  \nabla _x \;x^{\,\underline {\,m\;} }  = \left( {x\left( {x - 1} \right) \cdots \left( {x - m + 1} \right)} \right) - \left( {\left( {x - 1} \right)\left( {x - 2} \right) \cdots \left( {x - m} \right)} \right) = m\left( {x - 1} \right)^{\,\underline {\,m - 1\;} }  \hfill \\
  \nabla _x ^{\,n} \;x^{\,\underline {\,m\;} }  = m^{\,\underline {\,n\;} } \left( {x - n} \right)^{\,\underline {\,m - n\;} } \quad  \Rightarrow \quad \nabla _x ^{\,n} \;x^{\,\underline {\,m\;} }  = 0\quad \left| {\;m < n} \right. \hfill \\ 
\end{gathered} 
$$
therefore:
$$
\begin{gathered}
  \nabla _x ^n \,x^{n + 1}  = \nabla _x ^n \,\sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left\{ \begin{gathered}
  n + 1 \\ 
  k \\ 
\end{gathered}  \right\}\;x^{\,\underline {\,k\;} } }  = \nabla _x ^n \,\left( {\left\{ \begin{gathered}
  n + 1 \\ 
  n + 1 \\ 
\end{gathered}  \right\}\;x^{\,\underline {\,n + 1\;} }  + \left\{ \begin{gathered}
  n + 1 \\ 
  n \\ 
\end{gathered}  \right\}\;x^{\,\underline {\,n\;} } } \right) =  \hfill \\
   = \left( {\left\{ \begin{gathered}
  n + 1 \\ 
  n + 1 \\ 
\end{gathered}  \right\}\;\left( {n + 1} \right)^{\,\underline {\,n\;} } \left( {x - n} \right)^{\,\underline {\,1\;} }  + \left\{ \begin{gathered}
  n + 1 \\ 
  n \\ 
\end{gathered}  \right\}n^{\,\underline {\,n\;} } \;\left( {x - n} \right)^{\,\underline {\,0\;} } } \right) =  \hfill \\
   = \left( {1\;\left( {n + 1} \right)^{\,\underline {\,n\;} } \left( {x - n} \right)^{\,\underline {\,1\;} }  + \left( \begin{gathered}
  n + 1 \\ 
  n - 1 \\ 
\end{gathered}  \right)n^{\,\underline {\,n\;} } \;\left( {x - n} \right)^{\,\underline {\,0\;} } } \right) =  \hfill \\
   = n!\left( {\;\left( \begin{gathered}
  n + 1 \\ 
  n \\ 
\end{gathered}  \right)\left( {x - n} \right) + \left( \begin{gathered}
  n + 1 \\ 
  n - 1 \\ 
\end{gathered}  \right)} \right) \hfill \\ 
\end{gathered} 
$$
which, calculated at $x=n$ gives:
$$
\begin{gathered}
  \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^k \left( \begin{gathered}
  n \\ 
  k \\ 
\end{gathered}  \right)\;\left( {n - k} \right)^{n + 1} }  = \left. {\nabla _x ^n \,x^{n + 1} } \right|_{\,x = n}  =  \hfill \\
   = n!\left( \begin{gathered}
  n + 1 \\ 
  n - 1 \\ 
\end{gathered}  \right) = n!\frac{{\left( {n + 1} \right)n}}
{2} \hfill \\ 
\end{gathered} 
$$
thus proving your assertion, while generalizing it to other values of $x$.
</s>