partitioning a set of k objects into n non-empty subsets Let k be a positive natural number. Show that $$\{k,2\} = 2^{k-1} - 1$$ and that $$\{k, k-1\} = {k \choose 2}$$
where $\{k,  2\}$ is the number of ways to partition a set of k objects into 2 non-empty subsets, $\{k,  k-1\}$ is the number of ways to partition a set of k objects into k-1 non-empty subsets.
Attempt of solution:
I tried to show that the LHS is equal to the RHS 
$$\{k, 2\} = 2\{k-1, 2\} + \{k-1, 1\}$$
I am not sure how to equate these two 
please help
 A: Number the elements of $S$ as $1,2,\ldots k$ and consider a partition of a set $S$ into 2 parts say $S_1$ and $S_2$. Now construct a $k$ bit string $a$ such that $a_i = 0$ if element $i \in S_1$ and $a_i = 1$ if $i \in S_2$. It is easy to see that for each such partition there exists such a $k$-bit string and vice versa. (there is a bijection)
The number of such strings is $2^k$ but since we need non empty sets, exclude the $(0,0,\ldots,0)$ and $(1,1,\ldots,1)$ strings. Hence we have $2^k - 2$. But since the sets themselves are not uniquely numbered, we have counted each configuration twice. Hence the required number is 
$$\frac{2^k - 2}{2} = 2^{k-1} -1$$
For the second part, notice that partitioning a $k$ element set into $k-1$ parts simply amounts to picking two elements in it, assigning them to the same part and keeping all others as singletons. So the number of ways this can be done is $k \choose 2$.
Hope that helps.
A: Hopefully the following hints will help you. 
(a) Denote by $\{k,2\}$ the number of ways to partition a $k$-set into 2 nonempty subsets. Then to show that $$\{k,2\}=2^{k-1}-1$$
is essentially to show the following recurrence:
$$\{k+1,2\}=\{k,2\}+1$$
To prove this recurrence, we consider the following simple example. The set containing 3 elements $\{1,2,3\}$ can be partitioned into 2 nonempty subsets in 3 ways, i.e., $\{3,2\}=3$:
$$(\{1\},\{2,3\})$$
$$(\{2\},\{1,3\})$$
$$(\{3\},\{1,2\})$$
How many ways can $\{1,2,3,4\}$ be partitioned into 2 nonempty subsets? We just need to consider where to put the newcomer 4: obviously there are two ways 4 can be added to ({1},{2,3}): $$(\{1,4\},\{2,3\})$$
and $$(\{1\},\{2,3,4\})$$
This works for every partition of $\{1,2,3\}$, which accounts for the $2\{k,2\}$ in $\{k+1,2\}=2\{k,2\}+1$. What about the additional $1$? 
(b) Denote by $\{k,m\}$ the number of ways to partition a $k$-set into $m$ nonempty subsets. Note that $\{k,m\}$ is known as the Stirling number of the second kind and we have the following recurrence
$$\{k,m\} = k\{k-1,m\} + \{k-1,m-1\}$$
To see why this is case, consider the last element $k$. We can either put $k$ into a class by itself (in $\{k-1,m-1\}$ ways), or put it together with some nonempty subset of the first $k-1$ subsets, in which case there are $m\{k-1,m-1\}$ possibilites.
