Bell numbers (number of partitions of set of cardinality n) recurrence relation proof
For concreteness, let's suppose we are partitioning the set $\{1, 2, \dots, n+1\}$. Focus first on the block containing the element $1$. Let $k$ denote the number of elements other than $1$ that belong to this block. We can choose these elements in $\binom{n}{k}$ ways. Having formed this block, we partition the remaining $n + 1 - (k + 1) = n -k$ elements in $B_{n-k}$ ways. Summing over $k$ gives $$ \sum_{k = 0}^n \binom{n}{k} B_{n-k}. $$ By the symmetry of the binomial coefficients, this expression is equivalent to $$ \sum_{k = 0}^n \binom{n}{k} B_{k}. $$
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}