Combinatorial proof of $\sum_{k=0}^{n} k \binom{n+1}{k+1} n^{n-k} = n^{n+1}$

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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