TITLE: Let $n \in \mathbb{Z}^+$, prove the identity $ \sum_{k=1}^{n-1} \binom {n} {k} \frac{kn^{n-k}}{k+1}=\frac{n(n^{n}-1)}{n+1}$
QUESTION [4 upvotes]: Let $n \in \mathbb{Z}^+$, prove the identity $$ \sum_{k=1}^{n-1} \binom {n} {k} \frac{kn^{n-k}}{k+1}=\frac{n(n^{n}-1)}{n+1}$$
First of all  $$ \sum_{k=1}^{n-1} \binom {n} {k} \frac{kn^{n-k}}{k+1}=n^{n}\Bigg(\sum_{k=1}^{n-1} \binom {n} {k} \frac{kn^{-k}}{k+1} \Bigg)$$
$$=n^n\Bigg(\sum_{k=1}^{n-1} \binom {n}{k} \bigg(1-\frac{1}{k+1}\bigg)\bigg(\frac{1}{n^k}\bigg)\Bigg)$$
$$=n^n \sum_{k=1}^{n-1} \binom {n} {k} \frac{1}{n^k}-n^n \sum_{k=1}^{n-1} \binom {n}{k}  \bigg( \frac{1}{k+1}\bigg)\bigg(\frac{1}{n^k} \bigg)$$
We have for the first sum $$(1+\frac{1}{x})^n = \sum_{k=0}^n \binom{n}{k}\frac{1}{x^k}.$$
For the second sum 
$$(1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k.$$
Integrating both sides from $0$ to $x$, we see that 
$$\frac{(1+x)^{n+1}-1}{n+1} = \sum_{k=0}^n \binom{n}{k}\frac{x^{k+1}}{k+1}.$$
Putting $x=1$ yields $$\frac{2^{n+1}-1}{n+1}=\sum_{k=0}^n \binom{n}{k}\frac{1}{k+1}$$
Here where I have stopped. I could not get them similar for what I have. Would someone help me out !

REPLY [2 votes]: Here's a direct proof (no integration, no induction, just the binomial theorem and algebra):
\begin{align}\sum_{k=1}^{n-1} \binom {n} {k} \frac{kn^{n-k}}{k+1}&=\sum_{k=1}^{n-1} \binom {n} {k} \big(1-\frac1{k+1}\big)n^{n-k}
\\&=\sum_{k=1}^{n-1} \binom {n} {k} n^{n-k}-\sum_{k=1}^{n-1} \binom {n} {k} \frac1{k+1}n^{n-k}
\\&=\Big(\sum_{k=0}^{n} \binom {n} {k} n^{n-k}\Big)-\binom{n}{0}n^{n-0}-\binom{n}{n}n^{n-n}-\sum_{k=1}^{n-1} \frac{n!}{k!\, (n-k)!} \frac1{k+1}n^{n-k}
\\&=(1+n)^n-n^n-1-\sum_{k=1}^{n-1} \frac{n!}{(k+1)!\, (n-k)!} n^{n-k}
\\&=(n+1)^n-n^n-1-\sum_{k=1}^{n-1} \frac{n!}{(k+1)!\, (n-k)!} n^{n-k}
\\&=(n+1)^n-n^n-1-\sum_{k=1}^{n-1} \frac{(n+1)!/(n+1)}{(k+1)!\, (n-k)!} n^{n-k}
\\&=(n+1)^n-n^n-1-\frac1{n+1}\sum_{k=1}^{n-1} \frac{(n+1)!}{(k+1)!\, ((n+1)-(k+1))!} n^{n-k}
\\&=(n+1)^n-n^n-1-\frac1{n+1}\sum_{k=1}^{n-1} \binom{n+1}{k+1} n^{n-k}
\\&=(n+1)^n-n^n-1-\frac1{n+1}\sum_{k=2}^{n} \binom{n+1}{k} n^{n-k+1}
\\&=(n+1)^n-n^n-1-\frac1{n+1}\sum_{j=1}^{n-1} \binom{n+1}{n+1-j} n^j\scriptsize{\quad\text{(where }j=n-k+1)}
\\&=(n+1)^n-n^n-1-\frac1{n+1}\sum_{j=1}^{n-1} \binom{n+1}{j} n^j
\\&=(n+1)^n-n^n-1-\frac1{n+1}\left(-\binom{n+1}{0}n^0-\binom{n+1}{n}n^n-\binom{n+1}{n+1}n^{n+1}+\sum_{j=0}^{n+1} \binom{n+1}{j} n^j\right)
\\&=(n+1)^n-n^n-1-\frac1{n+1}\Big(-1-(n+1)n^n-n^{n+1}+(n+1)^{n+1}\Big)
\\&=(n+1)^n-n^n-1-\frac1{n+1}\Big(-1-n^{n+1}\Big)-\Big(-n^n+(n+1)^{n}\Big)
\\&=\require{cancel}\cancel{(n+1)^n}-\bcancel{n^n}-1+\frac1{n+1}\Big(1+n^{n+1}\Big)+\bcancel{n^n}-\cancel{(n+1)^{n}}
\\&=\frac{n^{n+1}+1}{n+1}-1
\\&=\frac{n(n^{n}-1)}{n+1},
\end{align}
as desired.
$$$$
{"set_name": "stack_exchange", "score": 4, "question_id": 1968896}