Let $p(n)$ denote the number of different equivalence relations on a set with $n$ elements (The number of partitions of a set with $n$ elements). Show that $p(n)$ satisfies the recurrence relation
$$p(n) = \sum_{j=0}^{n-1}\binom{n-1}jp(n-j-1)$$
and the initial condition $p(0) = 1$. (Note: The numbers $p(n)$ are called Bell numbers after the American mathematician E. T. Bell.)
Element $n$ must be in some part of the partition. Of the remaining $n - 1$ elements, suppose $j$ of them are in the same part as element $n$. The number of ways in which this can occur is $\binom{n-1}j$. The number of ways of partitioning the rest of the elements is $p(n - j - 1)$. Multiply those together and sum over $j$.