Prove that $\sum_{k=0}^{n-1}\frac{n^{k-1}}{k!}(n-k)(n-k+1)=\frac{n^{n-1}}{(n-1)!}+\sum_{k=0}^{n-1}\frac{n^k}{k!}$ I'm having trouble proving the following identity:

$$\sum_{k=0}^{n-1}\frac{n^{k-1}}{k!}(n-k)(n-k+1)=\frac{n^{n-1}}{(n-1)!}+\sum_{k=0}^{n-1}\frac{n^k}{k!}$$

I've played with the binomial theorem and other similar identities, but nothing seems to work. I'm sure we can prove it by induction, but I was more looking for a proof which uses other well-known identities.
 A: We have that $$\begin{align}\sum_{k=0}^{n-1}\left[\frac{n^{k-1}}{k!}(n-k)(n-k+1)-\frac{n^k}{k!}\right]&=\sum_{k=0}^{n-1}\frac{n^{k-1}((n-k)^2+n-k-n)}{k!}\\&=\sum_{k=0}^{n-1}\frac{n^{k-1}(n^2-2kn+k^2-k)}{k!}\\&=\sum_{k=0}^{n-1}\frac{n^{k+1}}{k!}-2\sum_{k=1}^{n-1}\frac{n^k}{(k-1)!}+\sum_{k=2}^{n-1}\frac{n^{k-1}}{(k-2)!}\\&=\sum_{j=1}^{n}\frac{n^{j}}{(j-1)!}-2\sum_{k=1}^{n-1}\frac{n^k}{(k-1)!}+\sum_{l=1}^{n-2}\frac{n^{l}}{(l-1)!}\end{align}$$ which can be written as $$\sum_{j=1}^{n}\frac{n^{j}}{(j-1)!}-2\left(-\frac{n^{n}}{(n-1)!}+\sum_{k=1}^{n}\frac{n^k}{(k-1)!}\right)-\frac{n^n}{(n-1)!}-\frac{n^{n-1}}{(n-2)!}+\sum_{l=1}^{n}\frac{n^{l}}{(l-1)!}$$ or $$\frac{n^{n}}{(n-1)!}-\frac{n^{n-1}(n-1)}{(n-1)!}=\frac{n^{n-1}}{(n-1)!}$$ so $$\sum_{k=0}^{n-1}\frac{n^{k-1}}{k!}(n-k)(n-k+1)=\frac{n^{n-1}}{(n-1)!}+\sum_{k=0}^{n-1}\frac{n^k}{k!}$$ as desired.
A: The "trick" is to split $(n-k)(n-k+1)$ into a sum of falling factorials of $k$, to get them simplified with $k!$.
$$
\eqalign{
  & \sum\limits_{k = 0}^{n - 1} {{{n^{\,k - 1} } \over {k!}}\left( {n - k} \right)\left( {n - k + 1} \right)}  =   \cr 
  &  = \sum\limits_{k = 0}^{n - 1} {{{n^{\,k - 1} } \over {k!}}\left( {k\left( {k - 1} \right) - 2n\,k + n\left( {n + 1} \right)} \right)}  =   \cr 
  &  = \sum\limits_{k = 0}^{n - 1} {{{n^{\,k - 1} k\left( {k - 1} \right)} \over {k!}}}  - 2n\sum\limits_{k = 0}^{n - 1} {{{n^{\,k - 1} k} \over {k!}}}  + n\left( {n + 1} \right)\sum\limits_{k = 0}^{n - 1} {{{n^{\,k - 1} } \over {k!}}}  =   \cr 
  &  = \sum\limits_{k = 2}^{n - 1} {{{n^{\,k - 1} } \over {\left( {k - 2} \right)!}}}  - 2n\sum\limits_{k = 1}^{n - 1} {{{n^{\,k - 1} } \over {\left( {k - 1} \right)!}}}  + n\left( {n + 1} \right)\sum\limits_{k = 0}^{n - 1} {{{n^{\,k - 1} } \over {k!}}}  =   \cr 
  &  = n^{\,2} \sum\limits_{k = 0}^{n - 3} {{{n^{\,k - 1} } \over {k!}}}  - 2n^{\,2} \sum\limits_{k = 0}^{n - 2} {{{n^{\,k - 1} } \over {k!}}}  + n\left( {n + 1} \right)\sum\limits_{k = 0}^{n - 1} {{{n^{\,k - 1} } \over {k!}}}  =   \cr 
  &  = n\sum\limits_{k = 0}^{n - 3} {{{n^{\,k} } \over {k!}}}  - 2n\sum\limits_{k = 0}^{n - 2} {{{n^{\,k} } \over {k!}}}  + \left( {n + 1} \right)\sum\limits_{k = 0}^{n - 1} {{{n^{\,k} } \over {k!}}}  =   \cr 
  &  = n\left( {\sum\limits_{k = 0}^{n - 1} {{{n^{\,k} } \over {k!}}}  - {{n^{\,n - 2} } \over {\left( {n - 2} \right)!}} - {{n^{\,n - 1} } \over {\left( {n - 1} \right)!}}} \right) - 2n\left( {\sum\limits_{k = 0}^{n - 1} {{{n^{\,k} } \over {k!}}}  - {{n^{\,n - 1} } \over {\left( {n - 1} \right)!}}} \right) + \left( {n + 1} \right)\sum\limits_{k = 0}^{n - 1} {{{n^{\,k} } \over {k!}}}  =   \cr 
  &  = \sum\limits_{k = 0}^{n - 1} {{{n^{\,k} } \over {k!}}}  + \left( { - {{n^{\,n - 1} } \over {\left( {n - 2} \right)!}} - {{n^{\,n} } \over {\left( {n - 1} \right)!}} + {{2n^{\,n} } \over {\left( {n - 1} \right)!}}} \right) =   \cr 
  &  = \sum\limits_{k = 0}^{n - 1} {{{n^{\,k} } \over {k!}}}  + {{n^{\,n - 1} } \over {\left( {n - 1} \right)!}} \cr} 
$$
A: Since $\frac{n^{n-1}}{(n-1)!}=\frac{n^n}{n!}$ we equivalently show the following is valid:
\begin{align*}
\sum_{k=0}^n\frac{n^{k-1}}{k!}(n-k)(n-k+1)=\sum_{k=0}^n \frac{n^k}{k!}
\end{align*}

We obtain
  \begin{align*}
\color{blue}{\sum_{k=0}^n}&\color{blue}{\frac{n^{k-1}}{k!}(n-k)(n-k+1)}\\
&=\sum_{k=0}^n\frac{n^{k-1}}{k!}\left[n(n+1)-2nk+k(k-1)\right]\\
&=(n+1)\sum_{k=0}^n\frac{n^k}{k!}-2\sum_{k=1}^n\frac{n^k}{(k-1)!}+\sum_{k=2}^n\frac{n^{k-1}}{(k-2)!}\tag{1}\\
&=(n+1)\sum_{k=0}^n\frac{n^k}{k!}-2n\sum_{k=0}^{n-1}\frac{n^k}{k!}+n\sum_{k=0}^{n-2}\frac{n^{k}}{k!}\tag{2}\\
&=n\left(\frac{n^n}{n!}+\frac{n^{n-1}}{(n-1)!}\right)+\sum_{k=0}^n\frac{n^k}{k!}-2n\cdot\frac{n^{n-1}}{(n-1)!}\tag{3}\\
&\,\,\color{blue}{=\sum_{k=0}^n\frac{n^k}{k!}}\tag{4}
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we multiply out and set the lower indices accordingly.

*In (2) we shift indices to start with $k=0$.

*In (3) we observe that summands with $n\sum_{k=0}^{\color{blue}{n-2}}\frac{n^{k}}{k!}$ cancel.

*In (4) we again use the identity $\frac{n^{n-1}}{(n-1)!}=\frac{n^n}{n!}$ and all the terms besides the sum vanish.
