Let's say that $B(n)$ (the Bell number) is the number of ways to split $\{1, \ldots ,n\}$ in non-empty blocks. Prove that, for $n \geq 1$: $$B(n)=\sum_{k=0}^{n-1}\binom{n-1}{k}B(k)$$ I don't really know how to hadle this. My first idea was doing this with a logic reasoning, since we know that:
$1)B(n)$=number of partitions of $\{1,\ldots ,n\}$
$2)B(k)$=number of partitions of $\{1,\ldots ,k\}$
$3) \begin{pmatrix} n-1 \\ k\end{pmatrix}$ = number of ways of taking $k$ elements from $\{1,\ldots ,n-1\}$
But I am not sure this leads to a solution. Could someone please help me?
The method of distinguished element can be applied. The result is trivial for the singleton set and the empty set, so we will prove that $$B_{n+1}=\sum_{k=0}^{n}{\binom{n}{k}B_k}$$ for all integers $n\ge 1.$ The distinguished element is $n+1.$ This element inhabits a set of $k+1$ elements in a partition for some $k\in [n]^{*}=\{0,1,2,\ldots, n\}.$ There are $\binom{n}{k}$ ways to choose the other $k$ elements of the set, and the remaining $(n+1)-(k+1)=n-k$ elements can be partitioned in $B_{n-k}$ ways. By the symmetry of Pascal's triangle, we get $$B_{n+1}=\sum_{k=0}^{n}{\binom{n}{k}B_{n-k}}=\sum_{k=0}^{n}{\binom{n}{n-k}B_{k}}=\sum_{k=0}^{n}{\binom{n}{k}B_k}.$$
The proof is also described in the Wikipedia article on Bell numbers.