Cfrgtkky

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?

1^st 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$.

2^nd 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$.

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 pgeq 1$ gives $degdelta 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)^nsum_{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}. $$

$newcommand{bbx}[1]{,bbox[15px,border:1px groove navy]{displaystyle{#1}},}
newcommand{braces}[1]{leftlbrace,{#1},rightrbrace}
newcommand{bracks}[1]{leftlbrack,{#1},rightrbrack}
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]{leftvert,{#1},rightvert}$

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

$ds{Hugeleft. aright)}$
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}$.