Question
I want to prove the following well known expression for Stirling Numbers of the Second Kind:
$$
\left\{{n+1}\atop{k+1}\right\}=\sum_{i=k}^{n}{\left(k+1\right)^{n-i}\left\{{i}\atop{k}\right\}}
$$
My Solution
Left hand side
We divide $n+1$ kids into $k+1$ non – empty groups. The number of groupings are given by the definition of Stirling Numbers of the Second Kind:
$$
\left\{{n+1}\atop{k+1}\right\}
$$
Right hand side
Suppose the kids are assigned number $1,…,n+1$ from youngest to oldest. The youngest kid in a group become the group’s captain. The term in right hand side gives us the number of possible groupings such that the oldest captain wear number $i+1$:
$$
\left(k+1\right)^{n-i}\left\{{i}\atop{k}\right\}
$$
Explanation: for kid $i+1$ to be the oldest captain, kid $1,…,i$ must be divided into the other $k$ groups and each group has at least one of these kids. Kid $i+2,…,n+1$ can join any of the $k+1$ groups.
If we sum up all the number for all possible value of $i$, we get the number of all possible groupings:
$$
\sum_{i=k}^{n}{\left(k+1\right)^{n-i}\left\{{i}\atop{k}\right\}}
$$
Conclusion
Because both left and right hand side are use to count the same objects they must be equal. I need your help to verify if my solution is correct and also if there’s other alternatives.
Best Answer
We seek to verify that
$${n+1\brace k+1} = \sum_{q=k}^n (k+1)^{n-q} {q\brace k}.$$
We get for the RHS using the OGF of the Stirling numbers of the second kind
$$\sum_{q=k}^n [z^{n-q}] \frac{1}{1-(k+1)z} [z^q] \prod_{r=1}^k \frac{z}{1-rz}$$
Now we may lower $q$ to zero as the second term makes for a zero contribution in the added range:
$$\sum_{q=0}^n [z^{n-q}] \frac{1}{1-(k+1)z} [z^q] \prod_{r=1}^k \frac{z}{1-rz} = [z^n] \frac{1}{1-(k+1)z} \prod_{r=1}^k \frac{z}{1-rz} \\ = [z^{n+1}] \frac{z}{1-(k+1)z} \prod_{r=1}^k \frac{z}{1-rz} = [z^{n+1}] \prod_{r=1}^{k+1} \frac{z}{1-rz} = {n+1\brace k+1}.$$
This is the claim.