How to compute $\sum_{j=1}^{n} {{n}\choose {j}} \cdot (-1)^{j+1} \cdot \frac{(n-j)^{n-1}}{n^{n-1}}$ Hey I am wondering if the sum 
 $$\sum_{j=1}^{n} {{n}\choose {j}} \cdot (-1)^{j+1} \cdot \frac{(n-j)^{n-1}}{n^{n-1}}  = 1 $$
 I got this formula from some question I tried to solve, the question is long so I will not post it here, but I am stuck with this sum, thanks for helping! I really do not know how to continue solving this sum, so how can i continue from here?
 A: 1st proof. The identity is equivalent to
$$ \sum_{j=0}^{n} \binom{n}{j}(-1)^j (n-j)^{n-1} = 0. $$
Let us prove a slightly general identity. Let $m \in \{0, \cdots, n-1\}$. Then
\begin{align*}
\sum_{j=0}^{n} \binom{n}{j}(-1)^j (n-j)^m
&= \left. \left(\frac{d}{dx}\right)^{m}\sum_{j=0}^{n} \binom{n}{j}(-1)^j e^{(n-j)x} \right|_{x=0} \\
&= \left. \left(\frac{d}{dx}\right)^{m} (e^x - 1)^n \right|_{x=0} \\
&= 0,
\end{align*}
where the last line follows from the fact that $(e^x - 1)^n = x^n \varphi_n(x)$ for some smooth function $\varphi_n$.

2nd proof. Alternatively, fix $m \geq 0$ and define $a_n = \sum_{j=0}^{n} \binom{n}{j}(-1)^j (n-j)^m$. Its exponential generating function satisfies
\begin{align*}
\sum_{n=0}^{\infty} \frac{a_n}{n!}x^n
&= \sum_{n=0}^{\infty} \left( \sum_{i+j=n} \frac{(-1)^j i^m}{i!j!} \right) x^n \\
&= \left( \sum_{j=0}^{\infty} \frac{(-1)^j}{j!}x^j \right)\left( \sum_{i=0}^{\infty} \frac{i^m}{i!}x^i \right) \\
&= e^{-x} \left( x \frac{d}{dx} \right)^m e^x.
\end{align*}
Now consider the operator $L$ defined by $L(f) = e^{-x} x \frac{d}{dx} (e^x f)$. By a direct computation, we find that $L = x(1 + \frac{d}{dx})$. So
$$ \sum_{n=0}^{\infty} \frac{a_n}{n!}x^n = L^m(1). $$
But the operator $L$, applied to a polynomial of degree $d$, results in a polynomial of degree $d+1$. So $L^m(1)$ is a polynomial of degree $m$, and so, $a_n = 0$ for all $n > m$.
A: Let $\delta$ be the forward difference operator, bringing $p(x)$ into $(\delta p)(x)=p(x+1)-p(x)$. This operator 
has the property that $\deg p\geq 1$ gives $\deg\delta p=\deg p-1$, hence $m>\deg p$ implies $\delta^m p(x)=0$.
If we consider $p(x)=x^{n-1}$, then
$$ 0=\delta^{n} p(x)=\sum_{k=0}^{n}\binom{n}{k}(-1)^k p(x+k)=(-1)^n\sum_{k=0}^{n}\binom{n}{k}(-1)^k p(x+n-k) $$
hence
$$ \sum_{k=0}^{n}\binom{n}{k}(-1)^k (n-k)^{n-1} = 0 $$
and
$$ \sum_{k=1}^{n}\binom{n}{k}(-1)^{k+1} (n-k)^{n-1} = n^{n-1}. $$
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\sum_{j = 1}^{n}{n \choose j}\pars{-1}^{j + 1}\,
{\pars{n - j}^{n - 1} \over n^{n - 1}}  = 1:\ {\LARGE ?}}$.

$\ds{\Huge\left. a\right)}$
\begin{align}
&\bbox[10px,#ffd]{\sum_{j = 1}^{n}{n \choose j}\pars{-1}^{j + 1}\,
{\pars{n - j}^{n - 1} \over n^{n - 1}}}
\\[5mm] = &\
-\,{1 \over n^{n - 1}}\sum_{j = 1}^{n}{n \choose j}\pars{-1}^{j}\,
\bracks{z^{n - 1}}\bracks{\pars{n - 1}!\expo{\pars{n - j}z}}
\\[5mm] = &\
-\,{\pars{n - 1}! \over n^{n - 1}}
\bracks{z^{n - 1}}\expo{nz}\sum_{j = 1}^{n}{n \choose j}
\pars{-\expo{-z}}^{j}
\\[5mm] = &\
-\,{\pars{n - 1}! \over n^{n - 1}}
\bracks{z^{n - 1}}\expo{nz}\bracks{\pars{1 - \expo{-z}}^{n} - 1}
\\[5mm] = &\
-\,{\pars{n - 1}! \over n^{n - 1}}
\underbrace{\bracks{z^{n - 1}}\pars{\expo{z} - 1}^{n}}
_{\ds{= {{n - 1 \brace n} \over \pars{n - 1}!} = 0}}\ +\
{\pars{n - 1}! \over n^{n - 1}}\
\underbrace{\bracks{z^{n - 1}}\expo{nz}}_{\ds{n^{n - 1} \over \pars{n - 1}!}}
\\[5mm] = &\ \bbx{\large 1}
\end{align}

$\ds{m \brace k}$ is the
  Stirling Number of the Second Kind which satisfies
  
$\ds{{m \brace k} = 0\ \mbox{when}\ m < k}$.


$\ds{\Huge\left. b\right)\ {\large\mbox{The}\ "easy\ one\ !!!".\quad}}$ ( see details in the above answer )
\begin{align}
&\bbox[10px,#ffd]{\sum_{j = 1}^{n}{n \choose j}\pars{-1}^{j + 1}\,
{\pars{n - j}^{n - 1} \over n^{n - 1}}} =
-\,{\pars{n - 1}! \over n^{n - 1}}
\bracks{z^{n - 1}}\pars{\expo{z} - 1}^{n} + 1
\\[5mm] = &\
-\,{\pars{n - 1}! \over n^{n - 1}}
\bracks{z^{-1}}\pars{\expo{z} - 1 \over z}^{n} + 1
\\[5mm] = &\
-\,{\pars{n - 1}! \over n^{n - 1}}\
\underbrace{\bracks{z^{-1}}\bracks{\sum_{k = 0}^{\infty}
{z^{k} \over \pars{k + 1}!}}^{n}}_{\ds{=\ 0}}\ + 1 = \bbx{\large 1}
\end{align}
