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 $\displaystyle S_{n,r}=S_{n-1,r-1}+rS_{n-1,r}$ (the other two are obvious).

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

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

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

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

Thanks for your help Taluivren