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!
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.
$$S_0^{n}=1,S_1^{n}=n$$
$$S_k^{n+1}=S_{k-1}^n+kS_k^n,k&gt;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$