Question
I want to prove the following well known expression for Stirling Numbers of the Second Kind:
$$
\left\{{n+k+1}\atop{k}\right\}=\sum_{i=1}^{k}{i\left\{{n+i}\atop{i}\right\}}
$$
My Solution
Left hand side
Suppose we want to divide $n+k+1$ kids into $k$ indistinguishable rooms. The number of possibilities is given by the definition of Stirling Numbers of the Second Kind:
$$
\left\{{n+k+1}\atop{k}\right\}
$$
Right hand side
Say that the kids are numbered $1,…,n+k+1$ from youngest to oldest. The number of possibilities if kid $n+1+i$ is the oldest kid who does not sleep alone is given by the term on the right hand side:
$$
i\left\{{n+i}\atop{i}\right\}
$$
Explanation: kid $n+i+2,…,n+k+1$ all have their own room while kid $1,…,n+i$ occupy the remaining $i$ rooms. Then kid $n+i+1$ can choose any of these $i$ rooms to join.
If we sum the number of possibilities for all possible value of $i$ then we once again get the number of possible division of $n+k+1$ kids into $k$ rooms:
$$
\sum_{i=1}^{k}{i\left\{{n+i}\atop{i}\right\}}
$$
Conclusion
Since both the left and right hand side are used to count the same objects they must be equal. I would like to ask you to verify if my answer is correct and if there’s any alternatives.
Best Answer
You should also mention that rooms are never left empty. But besides that, your argumentation looks sound. Alternatively we could also recall the recurrence relation \begin{align*} {{n+k+1}\brace {k}}=k{{n+k}\brace {k}}+{{n+k}\brace{k-1}}\tag{1} \end{align*} where the meaning of the right-hand side is fixing the oldest kid with number $n+k+1$. This kid
is either in a room by itself, leaving ${{n+k}\brace{k-1}}$ ways to put the other $n+k$ kids into $k-1$ rooms, none of these rooms empty,
or we have ${{n+k}\brace{k}}$ ways to put the other $n+k$ kids into $k$ rooms, none of these rooms empty and then we have $k$ ways to put kid with number $n+k+1$ into one of these rooms.