3
$\begingroup$

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?

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.