Mathematical induction and Stirling numbers I want to find a formula for the following series 
$$ \sum_{i=1}^m {m \choose i} i! S(n,i)$$
Where $S(n,m)$ is the Stirling numbers of the second kind.
Now I evaluated this series at $m=1,2,3$
for $m=1$ we have $${1 \choose 1}S(n,1) = m$$ because $S(n,1) = 1 = 1^n$
for $m=2$ we have $${2 \choose 1}1! S(n,1) + {2 \choose 2}2! S(n,2) = 2 + 2(2^{n-1} -1)= 2 + 2^n - 2= 2^n$$ 
for $m=3$ we have $${3 \choose 1}1! S(n,1) + {3 \choose 2}2! S(n,2) + {3 \choose 3} 3! S(n,3) = 3 + 3.2!(2^{n-1}-1) + 3! \times \frac{1}{6} \times (3^n - 3\times2^n +3) = 3^n$$
And now I see a pattern which is $m^n$.
Now I want to prove that I have the right patten, So I proceed by induction, Clearly It works for the base case as I did it already.
Now assume it works for $m=k$, and so we assume that $\sum_{i=1}^k {k \choose i} i! S(n,i) = k ^n$, we now want to prove it works for $k+1$ that is, we want to show that $$\sum_{i=1}^{k+1} {k+1 \choose i} i! S(n,i) = (k+1) ^n$$ but I am wondering where to proceed from here. Any suggestions ?
I feel like we should use pascal's triangle on ${k+1 \choose i}$ and so we have ${k+1 \choose i} = {k \choose i} + {k \choose i-1}$
and so we now need to prove that  $$\sum_{i=1}^{k} \big({k \choose i} + {k \choose i-1} \big) i! S(n,i) = (k+1) ^n$$
Am I right there ?
And then we can break this into two separate sums, so now we need to prove that $$\sum_{i=1}^{k} {k \choose i}i! S(n,i) + \sum_{i=1}^{k} {k \choose i-1}  i! S(n,i) = (k+1) ^n$$
Now by our hypothesis we assumed that $\sum_{i=1}^{k} {k \choose i}i! S(n,i) = k^n$ and now we need to evaluate $\sum_{i=1}^{k} {k \choose i-1}  i! S(n,i)$, But the first term in this sum is $1$ because we have ${k \choose 0} 1! S(n,1) = 1$ and then we have $\sum_{i=2}^{k} {k \choose i-1}  i! S(n,i)$ which is basically same like $\sum_{i=2}^{k} {k \choose i-1}  i! S(n,i)$ and this is the same like $\sum_{i=1}^{k} {k \choose i}  i! S(n,i)$ minus the last term ${k \choose k}k! S(n,k)$ but then I get stuck here.
Any suggestions ?
and then we 
 A: Suppose we seek to evaluate
$$\sum_{q=1}^m {m\choose q}\times q!\times {n\brace q}.$$
We can include $q=0$ here because the Stirling number is zero then.
Now the species of set partitions is given by
$$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$
which gives the generating function
$$\exp(u(\exp(z)-1))$$
and hence
$${n\brace q} = n! [z^n] \frac{(\exp(z)-1)^q}{q!}.$$
Substitute this into the sum to get
$$n! [z^n] \sum_{q=0}^m {m\choose q} \times q!\times \frac{(\exp(z)-1)^q}{q!}
\\= n! [z^n] \sum_{q=0}^m {m\choose q} (\exp(z)-1)^q 
 = n! [z^n] \exp(mz) = m^n.$$
A: You don't need an induction but a combinatorial argument. Take two sets $E$ and $F$ of cardinal $n$ and $m$ respectively. Set $X$ the set of functions of $E$ in $F$. Try to show that the sum you have is the cardinal of $X$. 
Indeed to any function $f:E\rightarrow F$ you can associate its image $A:=f(E)$. Now the number of functions $f:E\rightarrow F$ that has for image $A$ is exactly $|A|!\times S(n,|A|)$.  
Dividing $X$ by the different images that the function can have you get :
$$|X|=\sum_{i=1}^m\begin{pmatrix}m\\i\end{pmatrix}i!S(n,i)$$
Now, clearly $|X|=m^n$ so you have your equality.
