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.
 A: 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.
