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!}$

Question

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.

Answer 1

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.

Answer 2

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} $$

Answer 3

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.