I am trying to tackle the following exercise from Norman L. Biggs, Discrete Mathematics , p.91
Suppose we are given a partition of the $n$-set $X$ into $k$ parts, and we delete the part containing a given element $x$. We get a partition of a subset $Y$ of $X$ into $k-1$ parts, where $r=|Y|$ is in the range $0\leq r \leq n-1$. Use this idea to show that $$S(n,k) = \sum\limits_{r=0}^{n-1} \binom{n-1}{r}S(r, k-1)$$
$S(n,k)$ is the total number of partitions of an n-set $X$ into $k$ parts, and the following recursive formula is provided
$$S(n,k) = S(n-1,k-1) + kS(n-1,k) ; \space \space (2 \leq k \leq n-1)$$
Any hints on how to begin tackling this exercse will be greatly appreciated ! I know that I need to show that the combinatorial formula is equivalent to the recursive definition given above (and which appears as a proven theorem in the book) ... but not sure what the best approach is here.
For concreteness, suppose we are partitioning the set of integers $\{1, \dots, n\}$.
Let $r$ be fixed and denote the number of elements not in the same subset as element $1$. First, choose which $r$ elements you would like to exclude from the subset containing $1$, which can be accomplished in $\binom{n-1}{r}$ ways. Next, partition those elements into exactly $k-1$ subsets, which can be accomplished in $S(r,k-1)$ ways.
Summing $r$ over the range $0, \dots, n-1$ gives the identity.