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.
