Stirling Numbers of the Second Kind $ \sum_{j= m}^n {j \brace m} (m+1)^{n-j} = {n+1\brace m+1} $ I am trying to proof some identies from concrete mathmatics p 265. But i cant get nowhere. What i have found out its a recurrence, in the Stirling Numbers Triangle, its a vertical one. I get what it means, e.g. n=4 m=2 the Number of Partitioning 5 Elements into 4 Partitions  ${5 \brace 3}$ can be created from from $  {2 \brace 2}*(2+1)^2  +  {3 \brace 2}*(2+1)^1 +   {4 \brace 2}(2+1)^0  $ but i cant interprete combinatorically the $(2+1)^2,(2+1)^1, (2+1)^0$. Any ideas. It sould also work with Induction but,....well there are 2 pages of identities, i am not sure what to choose.   
 A: Starting from the LHS we write with $n\ge m$ and an Iverson bracket
$$\sum_{j=m}^n {j\brace m} (m+1)^{n-j}
= \sum_{j\ge m} {j\brace m} (m+1)^{n-j}
[[j\le n|j\ge 0]]
\\ = \sum_{j\ge m} {j\brace m} (m+1)^{n-j} [z^n] \frac{z^j}{1-z}
\\ = [z^n] \frac{1}{1-z} \sum_{j\ge m} {j\brace m} (m+1)^{n-j} z^j
\\ = [z^n] \frac{(m+1)^n}{1-z}  
\sum_{j\ge m} {j\brace m} \frac{z^j}{(m+1)^j}.$$
Recall the OGF
$$\sum_{j\ge m} {j\brace m} x^j = \prod_{r=1}^m \frac{x}{1-rx}$$
which yields for the present case
$$(m+1)^n [z^n] \frac{1}{1-z}
\prod_{r=1}^m \frac{z/(m+1)}{1-rz/(m+1)}
\\ = [z^n] \frac{1}{1-(m+1)z}
\prod_{r=1}^m \frac{z}{1-rz}
= [z^{n+1}] \frac{z}{1-(m+1)z}
\prod_{r=1}^m \frac{z}{1-rz}
\\ = [z^{n+1}] \prod_{r=1}^{m+1} \frac{z}{1-rz}
= {n+1\brace m+1}.$$
This is the claim.
A: Let see, $n+1\brace m+1$ means that you take $n+1$ elements and you partition them in $n+1$ disjoint and non empty blocks. Denote the partitions in the following way
$${[n+1]\brace m+1}=\{\pi \vdash [n+1]:|\pi|=m+1\},$$ the set of partitions. Given a partition $\pi ,$ let $j$ the maximum integer such that there is not block $B\in \pi$ such that $\{n+1,k\}\subseteq B,$ hence $\pi = (\pi _{[j]},f:[n]\setminus [j+1]\longrightarrow [m+1]),$ where $\pi _{[j]}$ is the partition $\pi$ but restricted to the set $[j]$ =because we know that $j+1$ has to be in the same block as $n+1$ and the function sends an element to one of the blocks(notice that blocks can be ordered by lexicografic order.) and hence $${[n+1]\brace m+1} = \bigcup _{j = m}^{n-1}{[j]\brace m}\times [m+1]^{n-(j+1)}$$
