Prove ${{n+m+1}\brace m}=\sum_{k=0}^mk{{n+k}\brace k}$ via double-counting

I want to show by a double-counting argument that$${{n+m+1}\brace m}=\sum_{k=0}^mk{{n+k}\brace k}$$for $m,n\in\Bbb N$ (where $0\in\Bbb N$).

Note that ${{n}\brace k}$ is a Stirling number of the second kind (i.e. the number of partitions of $[n]:=\{1,2,\ldots,n\}$ into $k$ blocks). I am just starting to do double-counting proofs, so I just want to make sure I am doing this right. I would like some feedback on my proof: whether it is correct or not, what are some improvements I could make, etc. Here is my proof:

We know that ${{n+m+1}\brace m}$ is the number of ways to partition $[n+m+1]$ into $m$ blocks. Now we focus on the $n+k+1$ element of $[n+m+1]$ for some $0\leq k\leq m$. Every element past $n+k+1$ we put in its own block in the partition, which accounts for $(n+m+1)-(n+k+1)=m-k$ of the blocks. We partition the first $n+k$ elements into the remaining $k$ blocks in ${{n}\brace k}$ ways. Then we stick the element $n+k+1$ into one of these $k$ blocks (which can be done in $k$ ways). Hence, there are $k{{n+k}\brace k}$ ways to partition the set with $m$ blocks with our choice of $k$. We sum over all possibilities of $k$ to account for all choices of the $n+k+1$ element to obtain ${{n+m+1}\brace m}=\sum_{k=0}^mk{{n+k}\brace k}$ total partitions of $[n+m+1]$ into $m$ blocks.

Thanks in advance for any feedback. If you have another way to prove this I'd love to see that as well.

• Your proof is correct and very well written! – Mike Earnest Oct 10 '17 at 18:13
• I often wonder how many formulae were first proved by double counting rather than by analysis (e.g., generating functions). – marty cohen Oct 10 '17 at 21:23

For the double counting argument I would put it like this. Suppose we partition $n+m+1$ labeled elements into $m$ sets. Now let $n+q+1$ be the minimum value so that all elements labeled from $n+q+2$ to $n+m+1$ reside in singleton sets. This gives $m-q$ singletons. Here we clearly have $q\ge 1$ (when $q=0$ we get $m$ singletons which leaves nothing to cover the elements up to $n+1$) as well as $q\le m$ ($q=m$ is the top case where $n+m+1$ is not a singleton). Note also that $n+q+1$ is in a partition that contains at least one additional element or it would not have been minimal. Therefore the partition of the elements from the lower end (the chain of singletons is the upper end) is a partition of $n+q+1$ into $q$ elements with $n+q+1$ not being a singleton. This means we obtain an ordinary partition of $n+q$ into $q$ elements when we remove $n+q+1$ from its partition. There are ${n+q\brace q}$ of these and we have $q$ possibilities for $n+q+1,$ giving the formula

$${n+m+1\brace m} = \sum_{q=1}^m q {n+q\brace q}.$$

For an algebraic proof, use induction starting at $m=1$ where we find

$${n+2\brace 1} = 1 \times {n+1\brace 1}$$

which holds by inspection. Supposing it holds for $m$ we get in the induction step

$${n+m+1\brace m} + (m+1){n+m+1\brace m+1} = \sum_{q=1}^{m+1} q {n+q\brace q}.$$

The left is just the basic Stirling number recurrence and we obtain

$${n+m+2\brace m+1} = \sum_{q=1}^{m+1} q {n+q\brace q}$$

as desired.