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

Question

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

Answer 1

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

Answer 2

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