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}$ 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 !
 A: There is a straightforward direct computational argument:
$$\begin{align*}
\sum_{k=1}^{n-1}\binom{n}k\frac{kn^{n-k}}{k+1}&=\sum_{k=1}^{n-1}\binom{n}k\left(1-\frac{1}{k+1}\right)n^{n-k}\\
&=\sum_{k=1}^{n-1}\binom{n}kn^{n-k}-\sum_{k=1}^{n-1}\binom{n}k\frac{n^{n-k}}{k+1}\\
&=(n+1)^n-n^n-1-\frac{1}{n+1}\sum_{k=1}^{n-1}\binom{n+1}{k+1}n^{n-k}\\
&=(n+1)^n-n^n-1-\frac{1}{n+1}\sum_{k=2}^n\binom{n+1}kn^{n+1-k}\\
&=(n+1)^n-n^n-1-\frac{1}{n+1}\left((n+1)^{n+1}-n^{n+1}-(n+1)n^n-1\right)\\
&=-1+\frac{n^{n+1}+1}{n+1}\\
&=\frac{n(n^n-1)}{n+1}
\end{align*}$$
A: Suppose we seek to show that
$$\sum_{k=1}^{n-1}  {n\choose k}
\frac{k n^{n-k}}{k+1} = \frac{n(n^n-1)}{n+1}.$$
Multiply by $n+1$ to get
$$\sum_{k=1}^{n-1}  {n+1\choose k+1}
k n^{n-k} = n(n^n-1).$$
Extend to $k=n$ to obtain
$$\sum_{k=1}^{n}  {n+1\choose k+1}
k n^{n-k} = n^{n+1}.$$
In order to prove this we introduce
$$n^{n-k} =
\frac{(n-k)!}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n-k+1}} \exp(nz) \; dz.$$ 
This yields
$$\frac{1}{(n-k)!} n^{n-k} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n-k+1}} \exp(nz) \; dz.$$ 
or
$${n+1\choose k+1} n^{n-k} =
\frac{(n+1)!}{(k+1)!}
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n-k+1}} \exp(nz) \; dz.$$ 
Observe that this vanishes when $k\gt n$ 
so we may extend the sum to infinity, getting
$$\frac{(n+1)!}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n+1}} \exp(nz) 
\sum_{k\ge 1} \frac{k}{(k+1)!} z^k
\; dz.$$ 
The sum term is
$$\sum_{k\ge 1} \frac{z^k}{k!}
- \sum_{k\ge 1} \frac{z^k}{(k+1)!}
= \exp(z) - 1 - \frac{1}{z} (\exp(z)-z-1)
\\ = \exp(z) - \frac{1}{z} \exp(z) + \frac{1}{z}.$$
Extracting the coefficients we thus obtain
$$(n+1)!
\left( \frac{(n+1)^n}{n!} - \frac{(n+1)^{n+1}}{(n+1)!}
+ \frac{n^{n+1}}{(n+1)!} \right)
\\ = (n+1)^{n+1} - (n+1)^{n+1} + n^{n+1} = n^{n+1}.$$
This is the claim.
A: 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.
$$$$
A: $$
\begin{align}
\sum_{k=1}^n\binom{n}{k}\frac{kn^{n-k}}{k+1}
&=n^n\sum_{k=1}^n\binom{n-1}{k-1}\frac1{k+1}\frac1{n^{k-1}}\\
&=n^n\int_0^1\sum_{k=1}^n\binom{n-1}{k-1}\frac{t^k}{n^{k-1}}\,\mathrm{d}t\\
&=n^n\int_0^1t\sum_{k=0}^{n-1}\binom{n-1}{k}\frac{t^k}{n^k}\,\mathrm{d}t\\
&=n^n\int_0^1t\,\left(1+\frac tn\right)^{n-1}\,\mathrm{d}t\\
&=n\int_0^1t\,(n+t)^{n-1}\,\mathrm{d}t\\
&=n\int_n^{n+1}(\color{#C00000}{t}-\color{#00A000}{n})\,t^{n-1}\,\mathrm{d}t\\
&=\color{#C00000}{\frac{n(n+1)^{n+1}-n^{n+2}}{n+1}}-\color{#00A000}{\left(n(n+1)^n-n^{n+1}\right)}\\
&=\frac{n^{n+1}}{n+1}\tag{1}
\end{align}
$$
Subtract the $k=n$ term from $(1)$ and we get
$$
\sum_{k=1}^{n-1}\binom{n}{k}\frac{kn^{n-k}}{k+1}=\frac{n^{n+1}-n}{n+1}\tag{2}
$$
