Number of partitions of an $n$-element set into $k$ classes A partition of a set $S$ is formed by disjoint, nonempty subsets of $S$ whose union is $S$. For example, $\{\{1,3,5\},\{2\},\{4,6\}\}$ is a partition of the set $T=\{1,2,3,4,5,6\}$ consisting of subsets $\{1,3,5\},\{2\}$ and $\{4,6\}$. However, $\{\{1,2,3,5\},\{3,4,6\}\}$ is not partition of $T$.
If there are $k$ nonempty subsets in a partition, then it is called a partition into $k$ classes. Let $S_k^n$ stand for the number of different partitions of a set with $n$ elements into $k$ classes.  


*

*Find $S_2^n$.  

*Show that $S_k^{n+1}=S_{k-1}^n+kS_k^n$.  
-- 
My work:
From the definition of $S$, $S_2^n=2^n$. I think I am wrong somewhere, because when I put this formula into the second part to prove, I get,
$$k^{n+1}=(k-1)^n+k \cdot k^n.$$
Please tell me where I am wrong. I think this problem cannot be solved by star-and-bar method as that method finds value for $k$ but does not prove it. Please help!
 A: on(i):
$2^n$ gives you the number of all subsets of $S$, but you are looking for the number of subsets that are not empty and have no empty complement. Their total number is $2^n-2$. Note that a nonempty subset $A$ having a non-empy complement $A^c$ corresponds with partion $P=\{A,A^c\}$. However, $A^c$ corresponds with that partition too. So counting these sets gives twice the number of partitions. This amounts in: $$S_n^2=2^{n-1}-1$$
addendum on (ii)
Start with a set $S$ having $n$ elements. Now form $S'=S\cup\left\{ x\right\} $
where $x\notin S$. Partitions of $S'$ in $k$ classes can be made in two
ways:
1) Let $\left\{ x\right\} $ be one of the classes. If $P$ is a partition
of $S$ in $k-1$ classes then $P'=P\cup\left\{ \left\{ x\right\} \right\} $
is a partition of $S'$ in $k$ classes. Here there are $S_{k-1}^{n}$ possibilities.
2) Let $\left\{ x\right\} $ be not one of the classes. For every partition of $S$ in $k$ classes we can put $x$ in
one of these classes wich will induce a partition of $S'$ in $k$
classes. There are $S_{k}^{n}$ such partitions and for $x$ there
are $k$ candidates so there are $kS_{k}^{n}$ possibilities.
A: We can prove $S^n_2 = 2^{n-1} -1$ using Mathematical induction.
${\bf Base\ case} :\ n=1$
Clearly $S^1_2 = 0$ as number of classes need to be 2 but elements in set is 1.
${\bf Inductive\ step}:$ Assuming statement is true for $n=k$, now
Let $a_{k+1}$ is the new element that is added to set of size $k$ to create a new set of size $k+1$.
We can divide $k+1$ elements into 2 parts in two ways

*

*$a_{k+1} \cup \{a_1,a_2,...,a_k\}$

*appending $a_{k+1}$ to either of the 2 classes that we get from each $S^k_2$ partition.

In other words,
$S^{k+1}_2 = 1 + 2S^k_2$
But $S^k_2 = 2^{k-1}-1$
$\implies S^{k+1}_2 = 1 +2(2^{k-1}-1)$
$\implies S^{k+1}_2 = 2^{k}-1$
So, statement is true for $k+1$ and hence true for all natural numbers.
A: $$S_0^{n}=1,S_1^{n}=n$$
$$S_k^{n+1}=S_{k-1}^n+kS_k^n,k>1$$
for $k=2$ we get that
$$S_2^{n}=S_{1}^{n-1}+2S_2^{n-1}=n+2S_2^{n-1}$$
Solution for last recurrence is not correct because $S_2^{n}\neq2^n$ 
