How to compute $\sum_{j=1}^{n} {{n}\choose {j}} \cdot (-1)^{j+1} \cdot \frac{(n-j)^{n-1}}{n^{n-1}}$

Question

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?

Answer 1

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$.

Answer 2

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}. $$

Answer 3

$\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}