A Series with $k$-Permutations

The following problem and its solution have been posted by Leo Giugiuc at the Short Mathematical Idea facebook group:

Prove that

(1)

$\displaystyle\sum_{k=1}^{n}k\cdot n^{n-k}\cdot A^{k-1}_{n-1}=n^n,$

where $A_{x}^{y}$ is the number of $x$-permutations, i.e., the number of arrangements of $x$ elements out of $y:$ $\displaystyle A_{x}^{y}=\frac{y!}{(y-x)!}.$

(Leo published the problem and solution in Gazeta Matematica, 4/2014)

First divide (1) by $n!$ to obtain

(2)

$\displaystyle\sum_{k=1}^{n}\frac{k}{n}\cdot\frac{n^{n-k}}{(n-k)!}=\frac{n^{n-1}}{(n-1)!}.$

Observe that

$\displaystyle\frac{n^{n-k}}{(n-k)!}-\frac{n^{n-k-1}}{(n-k-1)!}=\frac{k}{n}\cdot\frac{n^{n-k-1}}{(n-k-1)!}\big[n-(n-k)\big]=\frac{k}{n}\frac{n^{n-k}}{(n-k)!},$

for $k=1,2,\ldots,n-1.$ It thus follows that

$\begin{align}\displaystyle \sum_{k=1}^{n}\frac{k}{n}\cdot\frac{n^{n-k}}{(n-k)!}&=\sum_{k=1}^{n-1}\frac{k}{n}\cdot\frac{n^{n-k}}{(n-k)!}+1\\ &=\sum_{k=1}^{n-1}\bigg(\frac{n^{n-k}}{(n-k)!}-\frac{n^{n-k-1}}{(n-k-1)!}\bigg)+1\\ &=\sum_{k=1}^{n-1}\frac{n^{n-k}}{(n-k)!}-\sum_{k=2}^{n}\frac{n^{n-k}}{(n-k)!}+1\\ &=\frac{n^{n-1}}{(n-1)!}-1+1=\frac{n^{n-1}}{(n-1)!}. \end{align}$

71547911