# Thread: Sequence proof help

1. ## 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.

2. Hi,

let's look at $S_{n,r}=S_{n-1,r-1}+rS_{n-1,r}$ (the other two are obvious).

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

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

First of these summands equals $S_{n-1,r-1}$ because each partition occuring in the first summand is obtained by partitioning $A\smallsetminus \{a\}$ into $r-1$ nonempty subsets and adding the singleton $\{a\}$ to this partition.

Each partition occuring in the second summand can be described like this: Partition the set $A\smallsetminus \{a\}$ into $r$ nonempty subsets and adjoin the element $a$ to one of those subsets - there are $r$ possibilities how to do so for each such partition of $A\smallsetminus \{a\}$. So the second summand equals $rS_{n-1,r}$.

3. Thanks for your help Taluivren