Mathematical induction and Stirling numbers

Question

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

Answer 1

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.$$

Answer 2

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.