$S(n+1, k) = \sum_{i=k-1}^{n} \binom{n}{i} S(i, k-1)$

Question

So I need help with this: I need to prove $S(n+1, k) = \sum_{i=k-1}^{n} \binom{n}{i} S(i, k-1)$.
I know that if I take an extra element $a_{n+1}$ to a set of n elements then I have 2 options.
Either $a_{n+1}$ is the only element in a subset, then I need to divide n elements in k-1 boxes, wich is $S(n,k-1)$ or I put $a_{n+1}$ in a subset wich has already elements in it, wich is then $k*S(n,k)$ because per partition I get k new partitions.
Now I don't know how to explain this with the sum I was given. Can somebody help?

Answer 1

Let $n-i$ denote the number of elements in $\{a_1,a_2,\dots,a_n\}$ that are in the same box as $a_{n+1}$. Then there are exactly $\binom{n}{n-i}=\binom{n}{i}$ ways of choosing the elements in the same box as $a_{n+1}$.

The remaining $i$ elements in $\{a_1,a_2,\dots,a_n\}$ need to put into the remaining $k-1$ boxes. This can be done in exactly $S(i, k-1)$ ways.

Also, each box needs to have one element. So, the number of elements in the remaining $k-1$ boxes is atleast $k-1$. So, we get the condition $k-1\le i\le n$.

Thus, we obtain $S(n+1, k) = \sum_{i=k-1}^n \binom{n}{i} S(i, k-1)$.