<s>[INST] 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 !
 [/INST] 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.
</s>