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.
 A: Suppose you are choosing a team consisting of $1$ or more people among $n+1$ people(enumerated as person 1, person 2, etc). You also want to choose a captain in the team. The selection process is the following: You score each person with a number from $1$ to $n+1$ and you want to choose the team to be those who scored $n+1$. Among  them, you want to select the captain. You can do this by first selecting who were the ones to score $n+1$ (say $k$ of them) and then the captain, this will yield:
$$\sum _{k=0}^{n+1}\binom{n+1}{k}\cdot k\cdot n^{(n+1)-k}=\sum _{k=0}^{n}\binom{n+1}{k+1}\cdot (k+1)\cdot n^{(n+1)-(k+1)},$$
or you could have chosen the captain and then score the other people in $(n+1)\cdot (n+1)^n$ ways. 
Now suppose you do not want the captain to be the tallest of the team, were height is given proportional to their number i.e., person 1 is smaller than person 2, etc..(perhaps this is not a basketball team). We can choose the team, consisting in $k$ people, and then the captain in the following way:
$$\sum _{k=0}^{n}\binom{n+1}{k+1}\cdot k\cdot n^{(n+1)-(k+1)},$$
or we could have chosen first the captain. By the above problem, we know that there are in total $(n+1)^{n+1}$ ways to do this. Consider the opposite problem: Let's choose the captain to be the tallest in the team, we claim that this can be done in $(n+1)^{n+1}-n^{n+1}$, and so we would have at the end $(n+1)^{n+1}-((n+1)^{n+1}-n^{n+1})=n^{n+1}$ ways. 
Naively, we can represent the choosing of the captain by saying it is the $s-$th person and then choosing the rest of the team $k$ people in $\binom{s-1}{k}$ ways in the following way
$$\sum _{s=1}^{n+1}\sum _{k=0}^{s-1}\binom{s-1}{k}n^{n+1-(k+1)},$$
but we could have chosen the score of the non-selected people that are smaller than $s$ giving us
$$\sum _{s=1}^{n+1}\sum _{k=0}^{s-1}n^{n+1-s}\binom{s-1}{k}n^{s-(k+1)}=\sum _{s=1}^{n+1}n^{n-(s-1)}(n+1)^{s-1}=n^n\sum _{s=0}^n\left (\frac{n+1}{n}\right )^s=(n+1)^{n+1}-n^{n+1},$$
where the last step is the geometric sum. Combinatorially, the middle step corresponds to letting elements below $s$ to be in the team (having score $= n+1$ and not allowing people bigger than $s$). The last step by considering where is the last score  $=n+1$.
A: I will let others answer the combinatorial proof, but to your "A proof using algebra is also welcome", here is one.
Change the order of summation from $k$ to $n-k$ and subtract $n^{n+1}$ from both sides, your identity is equivalent to
$$
\sum_{k=0}^{n+1}\binom{n+1}{k}(n-k)n^k=0\tag{*}
$$
There are probably many different ways to prove this, for example write
\begin{align}
&x(x+1)^{n+1}-(n+1)x(x+1)^n\tag{1}\\
&=x(x+1)^{n+1}-x\frac{d}{dx}(x+1)^{n+1}\\
&=x\sum_{k=0}^{n+1}\binom{n+1}{k}x^k-x\frac{d}{dx}\sum_{k=0}^{n+1}\binom{n+1}{k}x^k\\
&=x\sum_{k=0}^{n+1}\binom{n+1}{k}x^k-x\sum_{k=0}^{n+1}\binom{n+1}{k}kx^{k-1}\\
&=\sum_{k=0}^{n+1}\binom{n+1}{k}x^k(x-k)\tag{2}\\
\end{align}
Now just evaluate both $(1)$ and $(2)$ at $x=n$ to get $(*)$.
A: $\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}.$
