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.

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 $(*)$.
