Evaluate $\sum^{n-1}_{k=1} {n\choose k}\frac{kn^{n-k}}{k+1}$ How can we evaluate:

$$\sum^{n-1}_{k=1} {n\choose k}\frac{kn^{n-k}}{k+1}$$

I observe that the expression has a similar format with the following formula:
$$\sum^{n}_{j=0} {n\choose j}\frac{u^j}{j+1}=\frac{1}{n+1}\sum^n_{k=0}(u+1)^k$$ but I have no idea how to process further. A blind evaluation using Wolfram Alpha gives us $\frac{n(n^n-1)}{n+1}$
 A: $\displaystyle \sum\limits^{n-1}_{k=1} {n\choose k}\frac{k x^{n-k}}{k+1}=\sum\limits^{n-1}_{k=1} {n\choose k}x^{n-k}-\frac{1}{n+1}\sum\limits^{n}_{k=2} {n+1\choose k}x^{(n+1)-k}=...$ 
I am sure you can finish - and it's left to set $x:=n$ .
I had used $k=(k+1)-1$ and ${n\choose k}\frac{n+1}{k+1}={n+1\choose k+1}$ .
A: Write
$$k n^{n-k}=-\partial_\alpha \left[\frac{n^n}{(n\alpha)^{k}}\right]_{\alpha=1}$$
This will eliminate the extra factor $k$ so you can work with your hint.
Although you must include $k=0$ (which is $0$) and $k=n$ terms:
\begin{align}
\sum_{k=1}^{n-1}{n\choose k}\frac{k n^{n-k}}{k+1}&=-n^n\partial_\alpha\left[\sum_{k=1}^{n-1}{n\choose k}\frac{(1/n\alpha)^k}{k+1}\right]_{\alpha=1}\\
&=\frac{-n^n}{n+1}\partial_\alpha\left[\sum_{k=0}^{n}(\frac1{n\alpha}+1)^k\right]_{\alpha=1}+\frac{n^n}{n+1}\partial_\alpha (1/n\alpha)^n\lvert_{\alpha=1}
\end{align}
Now the sum evaluates to
$$\partial_\alpha\left[\frac{-1+(\frac1{n\alpha}+1)^{n+1}}{\frac1{n\alpha}}\right]_{\alpha=1}=-n+n(\frac1n+1)^{n+1}-n(n+1)(\frac{1}n+1)^n\frac1n$$
This expression can be simplified by noting $\frac{1}n(n+1)=(\frac1n+1)$ and that then only $-n$ survives.
Evaluating now the $k=n$ term gives:
$$\frac{n^n}{n+1}\frac{-n}{n^{n}}=-\frac{n}{n+1}$$
Sum the two together and you get
$$\frac{-n^n}{n+1}(-n)-\frac n{n+1}=\frac{n^{n+1}-n}{n+1}$$
