Combinatorial proof of $\sum_{k=0}^{n} k \binom{n+1}{k+1} n^{n-k} = n^{n+1}$ Show :
$$\sum_{k=0}^{n} k \binom{n+1}{k+1} n^{n-k} = n^{n+1}$$
for natural number $n$. I randomly discovered this identity, and managed to prove it using simple algebra. I tried a combinatorial proof of this, but it seems too difficult for me.
The RHS is basically distributing $n+1$ people to $n$ different groups where an empty group is possible, but I could not show that the LHS is the same. Picking $k+1$ people out of $n+1$ equals $\binom{n+1}{k+1}$, and distributing others($n-k$ people) is equal to $n^{n-k}$ ; and now I am stuck with that $k$. Also I have no idea what to do with $k+1$ people I just picked; if I distribute them to $n$ groups then it will be overlapped with other terms of the sum.
A proof using algebra is also welcome, just in case.

$\underline{\text{Preliminary Results}}$
PR-1
$\displaystyle\sum_{i=0}^r \binom{r}{i}r^{r-i} = (1 + r)^r.$ 
This is directly from binomial expansion.
PR-2
$\displaystyle\sum_{k=0}^n \binom{n+1}{k+1}n^{n-k} = (1 + n)^{n+1} - n^{n+1}.$
Proof
First, re-index it to 
$\displaystyle\sum_{k=1}^{n+1} \binom{n+1}{k}n^{n+1-k}.$
Then, re-express it as 
$\displaystyle\left[\sum_{k=0}^{n+1} \binom{n+1}{k}n^{n+1-k}\right] - \binom{n+1}{0}n^{n+1}.$
Then, use PR-1 to convert this to 
$\displaystyle (1+n)^{n+1} - n^{n+1}.$
PR-3
$\displaystyle k\binom{n+1}{k+1} = \left[(n+1) \times \binom{n}{k}\right] - \binom{n+1}{k+1}.$
Proof
$\displaystyle k\binom{n+1}{k+1} = 
\frac{(n+1)!}{(n-k)!} \times \frac{k}{(k+1)!}$
$\displaystyle =~  
\frac{(n+1)!}{(n-k)!} \times \left[\frac{k+1}{(k+1)!} - \frac{1}{(k+1)!}\right]$
$\displaystyle =~  
\frac{(n+1)!}{(n-k)!} \times \left[\frac{1}{k!} - \frac{1}{(k+1)!}\right]$
$\displaystyle =~  
\left[(n+1) \times \binom{n}{k}\right] - \binom{n+1}{k+1}.$

Using PR-3
$\displaystyle \sum_{k=0}^n k\binom{n+1}{k+1} n^{n-k} = S - T$ 
where $\displaystyle ~S = (n+1)\sum_{k=0}^n \binom{n}{k}n^{n-k}$ 
and $\displaystyle ~T = \sum_{k=0}^n \binom{n+1}{k+1} n^{n-k}.$
Using PR-1
$\displaystyle S = (n+1)\left[(1 + n)^n\right] = (n+1)^{n+1}.$
Using PR-2
$\displaystyle T = (1+n)^{n+1} - n^{n+1}.$
Thus, $\displaystyle S - T = n^{n+1}.$
