Doing some recreational math, i was trying to reproduce the combinatorial proof of the identity
$$ n^n=\sum_{k=1}^n\frac{n!}{(n-k)!}\cdot k\cdot n^{n-k-1}\,\,\,\,(*) $$
mentioned by OP in the Question Non combinatorial proof of formula for nn ?
To be honest this shouldn't be too difficult:
the number of all sequences with length $n$ out of numbers $1,2,..,n$ is clearly $\underbrace{ n \cdot n...\cdot n}_{n\,\,times}=n^n$ which establishs the l.h.s. . For the r.h.s we demand that the first $k$ numbers are distinct but that the rest of the sequence can be choosen freely as before (Denote this number by $a_k$). In the end we sum over all $a_k$. I get
$$ a_k=\underbrace{n\cdot(n-1)...\cdot(n-k+1)}_{choose\,\,k\,\,numbers\\distinct}\times\underbrace{n^{n-k}}_{choose\,\,n-k\,\,numbers\\freely}\\= \frac{n!}{(n-k)!}n^{n-k} \,\,\,\,(**) $$
But this is not the same then the terms under the summation sign in $(*)$ so what am i doing wrong?
Edit 1:
I think i got it, i have to discount for the sequences with $k'>k$ distinct numbers (they can still fall out of the random part of my product) .Is this correct?
Edit 2:
To finish this, the correct quantity is given by the difference of sequences with $k$ and $k+1$ distinct numbers:
$$ a_{k+1}-a_{k}=-\frac{n!}{n^{n-k}}\left(\frac{1}{(n-k-1)!n}-\frac{1}{(n-k)!}\right)=-\frac{k}{n(n-k)!}\frac{n!}{n^{n-k}} $$
Done!
Edit3:
To avoid algebra we can also reason as follows (credit to @darijgrinberg):
Add to $(**)$ the following condtion: the $k+1$ number is fixed to ne one of the numbers in the first part of the product so that we don't get a sequence with $k+1$ distinct numbers. There are $k$ possiblities. Afterwards we can choose all remaining $n-k-1$ numbers at our wish. This results in a replacement $n^{n-k}\rightarrow k\times n^{n-k-1}$
I cannot tell if you already figured it out, but in case you haven't:
$$ a_k = \underbrace{n\cdot (n-1)\cdot\ldots\cdot (n-k+1)}_\text{choose first $k$ numbers distinct}\times\underbrace{k}_{\begin{array}{c}\text{choose $(k+1)^{st}$ number equal to }\\\text{one of the first $k$ numbers}\end{array}}\times \underbrace{n^{n-k-1}}_\text{choose remaining numbers freely} $$ The middle term must be $k$ because you need the "freshness" to be exactly $k$, meaning the first $k$ numbers are distinct, but the first $k+1$ numbers are not. Therefore, the $(k+1)^{st}$ number needs to be equal to one of the previous $k$.