Combinatorics proof by induction

By induction on $m$. For $m=1$, there is only one solution, namely $x_1 = n$. Indeed, \[ S(1,n) = 1 = \frac{n!}{0!n!} = \frac{(n+1-1)!}{(1-1)!n!} \] as desired.

For $m > 1$, suppose the number of solutions to the equation $x_1 = x_2 + \dots + x_{m-1} = n$ for given $n$ is $\frac{(n+m-2)!}{(m-2)!n!}$. A solution to $x_1 = x_2 + \dots + x_m = n$ is a solution to $x_1 = x_2 + \dots + x_{m-1} = n - x_m$, so, taking the sum over all the possible values $k$ of $x_m$ from $0$ to $n$ we have \[ S(m,n) = \sum_{k=0}^n \frac{(n-k+m-2)!}{(m-2)!(n-k)!} = \sum_{k=0}^n \frac{(k+m-2)!}{(m-2)!k!}, \] where we obtain the second equality by replacing $k$ with $n-k$ and noticing that the sum stays the same.

Now we prove by induction on n that \[ \sum_{k=0}^n \frac{(m+k)!}{m!k!} = \frac{(m+n+1)!}{(m+1)!n!}. \] For $n=1$ both terms are equal to $1$, so the thesis holds. Suppose it holds for $n-1$. Then \[ \sum_{k=0}^n \frac{(m+k)!}{m!k!} = \sum_{k=0}^{n-1} \frac{(m+k)!}{m!k!} + \frac{(m+n)!}{m!n!} = \frac{(m+n)!}{(m+1)!(n-1)!}  + \frac{(m+n)!}{m!n!} \\ = \frac{(m+n)!}{m!(n-1)!}\left( \frac{1}{m+1} + \frac{1}{n} \right) = \frac{(m+n)!}{m!(n-1)!} \frac{m+n+1}{(m+1)n} = \frac{(m+n+1)!}{(m+1)!n!} \] so applying this result to $m-2$ we get \[ \sum_{k=0}^n \frac{(k+m-2)!}{(m-2)!k!} = \frac{(m+n-1)!}{(m-1)!n!} \] and the thesis follows.