Here is a pdf file that I did sometime ago.
Let B(n) be the n-th Bell number (the number of equivalence relations on an n-element set). Show that the Bell numbers satisfy:
B(0) = 1;
B(n+1) = Sum_{k=0 }^n C(n,k)B(k).
(Hint: count equivalence relations on {0,1,...,n} by first choosing which elements are NOT related to n.) I am not quite sure how to start. i was thinking induction, but got lost? any help would be great