Recurrence Relation Homework question 2

Question

This is a HW question.

Find a recurrence relation for $b_n, n \geq 0 $where $b_n$ is the number of ways to partition $s= {1,2,3,...n}$ into exactly 2 subsets.

I am looking for a hint on how to go about this question.

Answer 1

Hint: There are two interpretations of the problem: (1) any subsets will do or (2) the subsets must be non-empty. We deal with (1). Of course (2) is a close relative.

Let $a_n$ be the number of ways to partition a set of $n$ people into $2$ subsets. Subset is too abstract a term, call them teams. Now an $(n+1)$-th person comes along, George.

We can divide our $(n+1)$-element set into teams by dividing the original $n$-element set into teams, and adding George to one of the teams or the other. Thus $a_{n+1}=\dots$.

Answer 2

Hint: form a bijection with bit strings. Let $S_{1}$ and $S_{2}$ be the subsets. Let the string $(a_{1}, a_{2}, a_{3}, \ldots, a_{n})$ mean the following: If $a_{i} = 1$, then $i \in S_{1}$; if $a_{i} = 0$, then $i \in S_{2}$. We can see that this bit string completely determines the partition on $1, 2, \ldots, n$. So $b_{n}$ should count the number of distinct bit strings we can form.

Now, say we expand to the $n+1$th number. Our bit string expands to $(a_{1}, a_{2}, a_{3}, \ldots, a_{n}, a_{n+1})$. To get $b_{n+1}$, we again count bit strings - but if we know $b_{n}$ we can see that we can put $b_{n+1}$ in terms of $b_{n}$ by the following relation: $b_{n+1}$ = (choices for $a_{n+1}$)*$b_{n}$.

Now can you get $b_{n+1}$ in terms of $b_{n}$?

Answer 3

why dont you start with writing out $b_n$ for the first $n$ such as $1,2,3,4$ and then see how it looks for $b_n$ and then for $b_{n+1}$. Then just substituting in $b_{n+1}$ the right side with $b_n$.