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.
Best Answer
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$.