Prove that $\left\{{n+k+1}\atop{k}\right\}=\sum_{i=1}^{k}{i\left\{{n+i}\atop{i}\right\}}$

Question

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.

Answer 1

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.

Answer 2

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.