$\mathbf {Theorem:} $ $$ \sum_{k=0}^n S_1(n,k)x^k = x(x +1)···(x +n−1) $$
I want to prove the above theorem, and I know that I should use the recurrence relation $$ S_1(n,k)=S_1(n-1,k-1)+(n-1)S_1(n-1,k). $$ I also know that $$\sum_{k=0}^n S_1(n,k)=n! ,\quad S_1(n,1)=(n-1)! ,\quad S_1(n,n)=1,$$ and $$S_1(n,0)=S_1(0,n)=0 \quad \text{if} \quad n\neq0. $$ I just started doing this:$$ \sum_{k=0}^n S_1(n,k)x^k =S_1(n,0)+S_1(n,1)x+S_1(n,2)x^2+...+S_1(n,n)x^n.$$ However I do not know how to proceed further. Can anybody help at this point?
As Donald Splutterwit mentioned in the comments, you can prove this by induction in the same way you can prove the binomial formula by induction and Pascal's recurrence. In this case we have
\begin{align} x^{\overline{n}} &= \sum_{k = 0}^n S_1(n,k)x^k \\ x^{\overline{n + 1}} &= (x + n)\sum_{k = 0}^n S_1(n,k)x^k \\ &= \sum_{k = 1}^{n + 1} S_1(n,k - 1)x^{k} + \sum_{k = 0}^{n} nS_1(n,k)x^{k} \\ &= \sum_{k = 0}^{n + 1} S_1(n + 1,k)x^k. \end{align}