<s>[INST] Calculating a sum in the coefficient of some generating function I tried to calculate the coefficient of a generating function
\begin{align*}
\frac{1}{n} [u^{n-1}] e^{un} \frac{1}{(1-u)^2}
\end{align*}
and got to
\begin{align*}
\frac{1}{n} [u^{n-1}] e^{un} \frac{1}{(1-u)^2} &= \frac{1}{n} [u^{n-1}] \Bigg(\sum_{k\geq 0}\frac{1}{k!} (un)^k\Bigg) \Bigg(\sum_{k\geq 0} \underbrace{\binom{n+2-1}{2-1}}_{=~n+1} u^n\Bigg) \\
&= \frac{1}{n} [u^{n-1}] \sum_{k\geq 0} \sum_{l=0}^k \frac{n^l}{l!} (k-l+1) u^{k} = \frac{1}{n} \sum_{l=0}^{n-1} \frac{n^l}{l!} (n-l).
\end{align*}
According to wolfram alpha, this sum equals
\begin{align*}
 \frac{1}{n} \sum_{l=0}^{n-1} \frac{n^l}{l!} (n-l) = \frac{n^n}{n!}.
\end{align*}
Is there a quick and simple way to show this or could I have done a different calculation in the beginning to arrive at this solution?
 [/INST] One could also work with geometric series instead of using the general binomial theorem:
\begin{align*}
  [z^n]g(f(z)) &= \frac{1}{n}[u^{n-1}]\phi(u)^n g'(u) \\
  &= \frac{1}{n}[u^{n-1}]e^{nu} \left( \frac{1}{1-u}\right)' \\
  &= \frac{1}{n}[u^{n-1}]e^{nu} \left( \sum_{k \geq 0}u^k\right)'  \\
  &= \frac{1}{n}[u^{n-1}]\sum_{k \geq 0}n^k\frac{u^k}{k!} \sum_{k \geq 1}ku^{k-1} \\
  &= \frac{1}{n}[u^{n-1}]\sum_{k \geq 0}n^k\frac{u^k}{k!} \sum_{k \geq 0}(k+1)u^{k} \\
  &= \frac{1}{n}[u^{n-1}]\sum_{k \geq 0}\sum^{k}_{l = 0}{(k-l+1) \frac{n^l}{l!}} u^k \\
  &= \frac{1}{n} \sum^{n-1}_{l = 0}{(n-1-l+1) \frac{n^l}{l!}} \\
  &= \frac{1}{n} \sum^{n-1}_{l = 0}{(n-l) \frac{n^l}{l!}} \\
  &= \frac{n^n}{n!}.
\end{align*}
where at the end we used
\begin{align}
  \frac{1}{n} \sum^{n-1}_{l=0}{\frac{n^l}{l!}(n-l)} &= \frac{1}{n}\sum^{n-1}_{l=1}\frac{n^l}{l!}(n-l) + 1 \\
  &= \sum^{n-1}_{l=1}\frac{n^l}{l!} - \sum^{n-1}_{l=1}{\frac{n^{l-1}}{(l-1)!}} + 1\\
  &=  \sum^{n-1}_{l=1}\frac{n^l}{l!} - \sum^{n-2}_{l=0}{\frac{n^{l}}{l!}} + 1 \\
  &= \frac{n^{n-1}}{(n-1)!} \\
  &= \frac{n^{n-1}n }{n(n-1)!} \\
  &= \frac{n^n}{n!}
\end{align}
</s>