Combinatorial and Algebraic Proof of an Identity involving Stirling Numbers of the second kind ${n+1\brace k+1}=\sum_i \binom{n}{i}{i\brace k}$

Question

The question is to prove the identity

$$ {n+1\brace k+1}=\sum_i \binom{n}{i}{i\brace k}\tag{1} $$

via a combinatorial proof and an algebraic proof. The question is from Aigner's A Course in Enumeration.

The braces indicate Stirling numbers of the second kind. I have managed to prove the identity using the polynomial method (which I will show below), but have not made much progress on the combinatorial proof.

My attempt: The left hand side represents the number of ways to partition an $n+1$ element set (say $[n+1]=\{1,\dotsc, n+1\}$) into $k+1$ sets. Each of the summands on the right hand side represents choosing $i$ elements where $k \leq i\leq n$ from $[n]$ and then partitioning them into $k$ sets. There is probably some sort of classification of the partition of an $n+1$ element set in to $k+1$ sets but I am not seeing it.

Algebraic Proof:

We expand $(x+1)^n$ in two different ways. First, note that $$ (x+1)^n=\sum_{i=0}^n\binom{n}{i}x^i=\sum_{i=0}^n\binom{n}{i}\sum_{k=0}^i {i\brace k} (x)_k=\sum_{k=0}^n(x)_k\left[\sum_{i=k}^n \binom{n}{i}{i\brace k} \right]\tag{2} $$ by the binomial theorem where $(x)_k$ is the falling factorial of length $k$. For the second way write $(x+1)^n$ as $$ \sum_{k=0}^n{n\brace k}(x+1)_{k} =\sum_{k=0}^n{n\brace k}[(x)_k+k(x)_{k-1}]= \sum_{k=0}^n\left[{n\brace k}+(k+1){n\brace k+1}\right](x)_k\tag{3} $$ and conclude using the recurrence relation for Stirling numbers.

Answer 1

Your algebriac proof is fine. For the Combinatorial proof consider the set that conatins the element $n+1$.

Choose $n-i$ elements from $[n]$ and create a block containing $n+1$ and the $n-i$ chosen elements. Now partition the final $i$ elements into $k$ blocks. Thus \begin{eqnarray*} {n+1\brace k+1}=\sum_{i=k}^{n} \binom{n}{i}{i\brace k}. \end{eqnarray*}