Bell numbers (number of partitions of set of cardinality n) recurrence relation proof Let $X$ be a set of cardinality $n$. How many partitions does it have? The users on the website found that these are the so called bell numbers. They also pointed out the following recurrence relation:
$$B_{n+1}=\sum\limits_{k=0}^n\binom{n}{k}B_k$$
Could someone provide some insight and prove this?

I like Austin Mohr's answer. It is precise but a bit dense. Please allow me make it more explicit.
Define $X_n=\{ x_1, \cdots, x_n \}$. 
For $n=0$ the empty set has only 1 partition. That is
    $B_0=1$. With $n=1$, $X_n$ has only one element $X_1=\{x_1\}$ 
    and $B_1=1$.  Now $X_{2}$ has two elements. What we need to know is how this new 
    element $x_2$ changes the picture.
    \begin{equation}
    X_2 = \{x_1 , x_2 \} = X_1 \cup \{ x_2 \}.
    \end{equation}
The new element $x_2$ can go in any old subset of the old partition 
    of $X_1$.
    That is for each of the $B_i$ partitions  $i<2$, of $X_1$, $x_2$ 
    can go
    into it  as follows:


*

*Join the $\emptyset$. That is
    \begin{equation}
        \{ x_2\} \cup \emptyset = \{ x_2 \},
        \end{equation}
    We count this as $1 B_0=\binom{1}{0} B_0$.

*Join $x_1$. That is
    \begin{equation}
        \{ x_1, x_2 \}.
        \end{equation}
    We count this as $1 B_1 = \binom{1}{1} B_1$.
\begin{equation}
    B_2 = \binom{1}0 B_0 + \binom{1}{1} B_1 = 2.
    \end{equation}
Explicitly we have
\begin{eqnarray}
    P_1 &=& \{  \{ x_1 \}, \{ x_2 \} \} \\
    P_2 &=& \{ \{x_1, x_2 \} \}  .
    \end{eqnarray}
We now assume that we know $B_n$ for the set $X_n$ and construct the set
$X_{n+1}$ where the new element $x_{n+1}$ should be added to the set $X_n$.
We ask, how this  new element $x_{n+1}$ will shake things up.
Given a partition of $X_{n+1}$, the element $x_{n+1}$ should be present
in one (and only one) block of this partition. Let us 
take that block and assume that the block has $k$ elements (no counting the $x_{n+1}$ new 
element).  How many of these block prototypes would we have? We can pick any 
$k$ out of $n$ elements and this will represent the number of blocks with $k+1$ (
the 1 is for $x_{n+1}$) elements where $x_{n+1}$ is present. This number is 
$\binom{n}{k}$. We still have to count partitions. Every block of this type corresponds 
to a partition with $n+1-(k+1)=n-k$ elements. That is for every block of this
we have $B_{n-k}$ partitions. The total number of partitions is
\begin{equation}
      \sum_{k=0}^{n} \binom{n}{k} B_{n-k}.
    \end{equation}
Note that if $k=0$, this means that $x_{n+1}$ goes into a singleton
$\{x_{n+1}\}$, where $\binom{n}{0}=1$ and we have $B_n$ partitions all
without $x_{n+1}$. This happened just before adding $x_{n+1}$. On the
other extreme is $k=n$. This means that the block is the whole set
$X_n$ and there is no much to play with other than adding the element
$x_{n+1}$ to the whole set $X_n$ making it $X_{n+1}$.  Note that, since
\begin{equation}
    \binom{n}{k}=\binom{n}{n-k}
    \end{equation}
we can write
\begin{equation}
      \sum_{k=0}^{n} \binom{n}{k} B_{n-k} =
      \sum_{k=0}^{n} \binom{n}{n-k} B_{n-k} =
      \sum_{k=n}^{0} \binom{n}{n-k} B_{n-k} =
      \sum_{k=0}^{n} \binom{n}{k} B_{k}.
    \end{equation}
