Explanation for the number of partitions of $\{1,\dots,n\}$ into $k$ parts A partition of the set $\{1, 2, . . . , n\}$ into $k$ parts is a way of writing the set as a disjoint union of $k$ subsets. For example $\{1, 2, 3, 4, 5\} = \{1, 4\} \cup\{2, 3\} \cup \{5\}$ is a partition into $3$ parts.

Let $p(n, k)$ be the number of partitions of $\{1, 2, . . . , n\}$ into $k$ parts. Prove the following:
$$p(n, k) = k · p(n − 1, k) + p(n − 1, k − 1).$$

I have an answer to the proof in my textbook but it doesn't make a lot of sense to me. Could someone explain the steps to proving this?
 A: The number $n$ is either a partitioned class in itself -- then we are left with partitioning $\{1,2,\dots,n-1\}$ into $k-1$ parts, 
 or $n$ takes part of a class with at least $2$ elements, in this case, if we omit $n$, we obtain $\{1,2,\dots,n-1\}$ again, partitioned into $k$ parts. Now, $n$ can join any of the $k$ classes from each such partition -- so, if only a $k$-partition of $\{1,\dots,n-1\}$ is given, there are exactly $k$ different possibilities to join them $n$.
A: Suppose we have a partition of $\{1,\cdots,n\}$ into $k$ parts.
1) If $\{n\}$ is a part itself, then the remaining $k-1$ parts give a partition of $\{1,\cdots,n-1\}$, so this gives $p(n-1,k-1)$ possibilities.
2) If $n$ is included with other elements in one of the $k$ parts, then the remaining elements give a partition of $\{1,\cdots,n-1\}$ into $k$ parts, and then
$n$ can be included in any of the $k$ subsets to get a partition of $\{1,\cdots,n\}$.  Therefore this case gives $kp(n-1,k)$ possibilities.
A: Basically the trick goes like this:
Remark: I'm being a little informal here, if more details are needed just comment, and I'll write more. I'm just trying to convey the basic idea).
Suppose you have your set of $n$ elements. WLOG it's $\lbrace 1,2,\ldots, n\rbrace$. You want to know in how many ways you can partition it into $k$ subsets. Let's divide all possible partitions into two types.


*

*We'll call a partition of type 1 if $\lbrace n\rbrace$ is an element of the partition.

*We'll call an element of type 2 if $\lbrace n\rbrace$ is not an element of the partition.


Clearly, the number of partitions for $\lbrace 1,2,\ldots,n\rbrace$ equals the sum of the number of partitions of type 1 and of type 2.
So let's count those.
How many partitions of type 1 are there? Well, a partition of type 1 is just a partition of $\lbrace 1,2,\ldots,n-1\rbrace$, in to $k-1$ subsets, to which we add the element $\lbrace n\rbrace$. So, there are exactly $p(n-1,k-1)$ such partitions. 
How many partitions of type 2 are there? We know that the singelton $\lbrace n\rbrace$ is not an element of the partition, so it has to be that $n$ appears in some subset of order greater than 1. So, finding a partition of type 2 is essentially the same as finding a partition of $\lbrace 1,2,\ldots,n-1\rbrace$ into $k$ subsets, and just adding $n$ to one of the subsets of the partition. The number of partitions of $\lbrace 1,2,\ldots,n-1\rbrace$ into $k$ subsets is $p(n-1,k-1)$, and since we will get a partition of type 2 if we add $n$ to any subset of such a partition, we get that the number of partitions of type 2 is precisely 
$$k\cdot p(n-1,k).$$
Hope that clears thing up a little.
