Thread: Sequence proof help

Hi,

let's look at (the other two are obvious).

Let a set have elements. Pick one of them and denote it . Then the following certainly holds:

"number of ways to partition into nonempty subsets" = "number of ways to partition into nonempty subsets such that for each such partition the subset containing contains only " + "number of ways to partition into nonempty subsets such that for each such partition the subset containing contains also another element distinct from "

First of these summands equals because each partition occuring in the first summand is obtained by partitioning into nonempty subsets and adding the singleton to this partition.

Each partition occuring in the second summand can be described like this: Partition the set into nonempty subsets and adjoin the element to one of those subsets - there are possibilities how to do so for each such partition of . So the second summand equals .

Thanks for your help Taluivren