# 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?

• Is this even true for $n=2$? Seems false. – A. Pongrácz Dec 10 '18 at 11:36
• @A.Pongrácz opps my bad, i meant one – משה לוי Dec 10 '18 at 12:09

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

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


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