I want to work out the number of ways that I can assign $k$ labels to $m$ objects, where labels can be repeated. I've concluded that this is equivalent to seeking the number of ways that a set $A$ with $\vert A \vert = m$ can be partitioned into $k$ possibly empty subsets $A_i$. Based on some small examples that I've enumerated by hand, I suspect that the answer is $k^m$ but I'm having trouble proving it.
First of all, for the case with $k=3$ I need to show that $$ \sum_{i=0}^m 2^{m-i}{m \choose i} =^? 3^m \tag{1} $$
in order for my claimed identity to hold up. I'm not sure how to do this and would really appreciate some help. I've tried induction in the spirit of the $2^m$ identity but I just got a mess that I couldn't make any progress with.
For the general case, let's say that $\vert A_i \vert = s_i$.
For a fixed $s = (s_1, \dots, s_k)$, we have that there are $$ {m \choose s_1}{m - s_1 \choose s_2}\dots{m - s_1 - \dots - s_{k-1} \choose s_k} $$
possible partitions so I need to sum that product over all valid $s$. I think this is equal to
$$ \sum_{s_1=0}^m \sum_{s_2=0}^{m-s_1} \sum_{s_3=0}^{m-s_1-s_2} \dots \sum_{s_{k-1}=0}^{m-s_1-\dots-s_{k-2}} \prod_{r=1}^k {m - \sum_{j=0}^{r-1}s_j \choose s_r} =^? k^m \tag{2} $$
which is a rather monstrous quantity that I really don't know how to work with.
In summary, my questions are:
is there a simple way to prove the special case (1)?
how can I prove the general case (2)?
Update:
Brian M Scott pointed out in the comments that I could just use the binomial theorem with $(2+1)^m$ to answer my (1), so that question is answered!
For the general result, notice that in assigning the labels to the $m$ objects you are simply making a $k$-way choice $m$ times in a row; by the multiplication principle this can be done in $m^k$ different ways.