Prove that $\left\{{n+k+1}\atop{k}\right\}=\sum_{i=1}^{k}{i\left\{{n+i}\atop{i}\right\}}$

combinatorial-proofscombinatoricssolution-verificationstirling-numbers

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.

We can now iteratively apply (1). We obtain \begin{align*} \color{blue}{{{n+k+1}\brace {k}}}&=k{{n+k}\brace {k}}+{{n+k}\brace{k-1}}\\ &=k{{n+k}\brace {k}}+(k-1){{n+k-1}\brace{k-1}}+{{n+k-1}\brace{k-2}}\\ &=k{{n+k}\brace {k}}+(k-1){{n+k-1}\brace{k-1}}+(k-2){{n+k-2}\brace{k-2}}\\ &\qquad+\cdots+1{{n+1}\brace{1}}\\ &\,\,\color{blue}{=\sum_{i=1}^ki{{n+i}\brace{i}}} \end{align*} and the claim follows.

Related Question