Combinatorial proof of Stirling Number Identity (First Kind) For $m,n\ge 0$, 
$$\sum^m_{k=0} (n+k)\left[{n+k}\atop{k}\right]={{m+n+1}\brack m}\;.$$
I need to prove this combinatorially. I know the RHS counts the number of $m+n+1$ permutations with $m$ cycles. I'm stuck on how to show the LHS does so too. 
 A: Suppose that $\pi$ is a permutation of $[m+n+1]$ with $m$ cycles. Let $\ell$ be the largest element of $[m+n+1]$ that is not in a $1$-cycle of $\pi$. Then $\pi$ is obtained from a permutation $\sigma$ of $[\ell]$ by appending $1$-cycles $(\ell+1)(\ell+2)\ldots(m+n+1)$, where $\ell$ is not in a $1$-cycle of $\sigma$, and $\sigma$ has $$m-\Big((m+n+1)-\ell\Big)=\ell-n-1$$ cycles. This means that $\sigma$ can be obtained from a permutation $\tau$ of $[\ell-1]$ with $\ell-n-1$ cycles by inserting $\ell$ into some cycle of $\tau$. 
A little thought shows that $n+2\le\ell\le m+n+1$, so $\ell-1$ ranges from $n+1$ through $n+m$. Fix $\ell-1$ in this range, and let $\tau$ be any permutation of $[\ell-1]$ with $\ell-n-1$ cycles. There are $\ell-1$ ways to extend $\tau$ to a permutation $\sigma$ of $[\ell]$ with $\ell-n-1$ cycles by inserting $\ell$ into a cycle of $\tau$. This $\sigma$ can then be extended uniquely to a permutation $\pi$ of $[m+n+1]$ with $$(\ell-n-1)+\Big((m+n+1)-\ell\Big)=m$$ cycles such that $\ell$ is the largest element of $[m+n+1]$ not in a $1$-cycle. Summing over $\ell$, we have
$${{m+n+1}\brack m}=\sum_{\ell=n+2}^{n+m+1}(\ell-1){{\ell-1}\brack{\ell-n-1}}\;.$$
Make an appropriate change of index, and you’ll have the result.
Added: To see how I came up with this, it may help to realize that it’s just a generalization of the combinatorial proof of the recurrence
$${{n+1}\brack k}=n{n\brack k}+{n\brack{k-1}}$$
that is given here, among other places.
A: For the sake of completeness we present a proof of the basic recurrence using generating functions. The bivariate exponential generating function of the unsigned Stirling numbers of the first kind is given by
$$ G(z, u) = \exp\left(u \log\frac{1}{1-z}\right).$$
It follows that the exponential generating function of $n\left[n\atop k\right]$ is given by
$$ H(z, u) = z \frac{\partial}{\partial z} G(z, u) =
z\exp\left(u \log\frac{1}{1-z}\right) u (1-z) (-1) \frac{1}{(1-z)^2} (-1) \\=
u \frac{z}{1-z}\exp\left(u \log\frac{1}{1-z}\right).$$
The RHS of the basic recurrence is thus given by
$$n\left[n\atop k\right] + \left[n\atop k-1\right] =
n![z^n u^k] H(z, u) + n![z^n u^{k-1}] G(z, u) \\ =
n![z^{n+1} u^k] z H(z, u) + n![z^{n+1} u^k] z u G(z, u) \\ =
n![z^{n+1} u^k] \exp\left(u \log\frac{1}{1-z}\right)
\left(u \frac{z^2}{1-z} + zu\right) \\ =
n![z^{n+1} u^k] \exp\left(u \log\frac{1}{1-z}\right)
\frac{u z}{1-z} =
n![z^{n+1} u^k] H(z, u) \\= n! \frac{(n+1)}{(n+1)!} \left[n+1\atop k\right] =
 \left[n+1\atop k\right].$$ 
