Prove that $\left\{{n+k+1}\atop{k}\right\}=\sum_{i=1}^{k}{i\left\{{n+i}\atop{i}\right\}}$ 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.
 A: 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.

A: A generating function approach. The following identity is valid for $k\geq 1$:
\begin{align*}
\color{blue}{\prod_{q=1}^k\frac{1}{1-qz}=\sum_{j=1}^kjz\prod_{q=1}^j\frac{1}{1-qz}+1}\tag{1}
\end{align*}
We show (1) by induction on $k$.
Base step $(k=1)$: The left-hand side and right-hand side of (1) give
\begin{align*}
\prod_{q=1}^1\frac{1}{1-qz}&=\frac{1}{1-z}\\
\sum_{j=1}^1jz\prod_{q=1}^j\frac{1}{1-qz}+1&=\frac{z}{1-z}+1=\frac{1}{1-z}
\end{align*}
and the base step follows.
Induction hypothesis $(k=K)$: We assume the validity of
\begin{align*}
\prod_{q=1}^K\frac{1}{1-qz}=\sum_{j=1}^{K}jz\prod_{q=1}^j\frac{1}{1-qz}+1
\end{align*}
Induction step $(k=K+1)$: We obtain
\begin{align*}
\color{blue}{\prod_{q=1}^{K+1}}\color{blue}{\frac{1}{1-qz}}
&=\frac{1}{1-(K+1)z}\prod_{q=1}^K\frac{1}{1-qz}\\
&=\frac{(K+1)z+(1-(K+1)z)}{1-(K+1)z}\prod_{q=1}^K\frac{1}{1-qz}\\
&=(K+1)z\prod_{q=1}^{K+1}\frac{1}{1-qz}+\prod_{q=1}^K\frac{1}{1-qz}\\
&=(K+1)z\prod_{q=1}^{K+1}\frac{1}{1-qz}+\sum_{j=1}^{K}jz\prod_{q=1}^j\frac{1}{1-qz}+1\\
&\,\,\color{blue}{=\sum_{j=1}^{K+1}jz\prod_{q=1}^j\frac{1}{1-qz}+1}
\end{align*}
and the claim (1) follows.
We recall the generating function of the Stirling numbers of the second kind  in the form
\begin{align*}
\color{blue}{{n\brace k}=[z^n]\prod_{q=1}^k\frac{z}{1-qz}}\tag{2}
\end{align*}
where the coefficient of operator $[z^k]$ denotes the coefficient of $z^k$ of a series.

We obtain from (1) and (2)
\begin{align*}
\color{blue}{{n+k+1\brace k}}&=[z^{n+k+1}]\prod_{q=1}^{k}\frac{z}{1-qz}\tag{3.1}\\ 
&=[z^{n+1}]\prod_{q=1}^{k}\frac{1}{1-qz}\tag{3.2}\\ 
&=[z^{n+1}]\left(\sum_{j=1}^kjz\prod_{q=1}^j\frac{1}{1-qz}+1\right)\tag{3.3}\\
&=\sum_{j=1}^kj[z^{n}]\prod_{q=1}^j\frac{1}{1-qz}\tag{3.4}\\
&=\sum_{j=1}^kj[z^{n+j}]\prod_{q=1}^j\frac{z}{1-qz}\\
&\,\,\color{blue}{=\sum_{j=1}^kj{n+j\brace j}}\tag{3.5}
\end{align*}
and the claim follows.

Comment:

*

*In (3.1) we use the representation (2) via generating functions.


*In (3.2) we apply the rule $[z^{p-q}]A(z)=[z^{p}]z^qA(z)$.


*In (3.3) we use the identity (1).


*In (3.4) we use the linearity of the coefficient of operator and apply again the rule as in (2). We also skip the constant $1$, which does not contribute to $[z^{n+1}]$.


*In (3.5) we use again the representation (2).
Note: In other words the identity (1) is precisely OPs formula encoded via generating functions.
