Thread: Sequence proof help

Hi,

I'm having trouble with a math problem which involves proving that a particular recurrence is true for a function S(n,k). Having trouble getting started with this one - I think maybe I can use induction, but I'm not sure exactly how it would be applied to this problem.



Thanks in advance for any 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