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