What is $S_m(n)$ if $S_0(n) = 1$ and $S_{m+1}(n) = \sum_{k=1}^n S_m(k)$ and $m$ and $n$ are integers? What is $S_m(n)$ if $S_0(n) = 1$ and $S_{m+1}(n) = \sum_{k=1}^n S_m(k)$ and $m$ and $n$ are integers?
I tried to find a pattern:
$S_{m+1}(n) = S_{m}(1) + S_{m}(2) + ... + S_{m}(n)$
$=nS_{m-1}(1) + (n-1)S_{m-1}(2) + ... + S_{m-1}(n)$
$=(n + n-1 + n-2 + ... + 1)S_{m-2}(1) + (n-1 + n-2 + ... 1)S_{m-2}(2) + ... + S_{m-2}(n)$,
but the expression soon became hard to overview. Another attempt was to calculate each summand separately in:
$S_{m+1}(n) = S_{m}(1) + S_{m}(2) + ... + S_{m}(n)$
as follows:
$S_{m}(1) = S_{m-1}(1) = ... = S_1(1) = S_0(1) = 1$,
$S_{m}(2) = S_{m-1}(1) + S_{m-1}(2)  = 1 + S_{m-1}(2) = ... = m +1$
...
but soon I got stuck again. It is easily checked that for $m=2$ and $n=5$ we get $S_m(n) = S_2(5) = 15$. Is there a closed general solution? Using a computer is a possibility but for e.g. very large $n$ that seems difficult as well.
 A: Consider for each $m\geqslant 0$ the generating function $f_m(u,v) = u^m\sum_{n\geqslant 0} S_m(n) v^n $. Then your first condition on $S_0$ implies that $f_0(u,v) = (1-v)^{-1}$. The condition on $S_{m+1}(n)$ implies that
$$\frac{u}{1-v} f_m(u,v) = f_{m+1}(u,v).$$
Indeed, multiplying by $(1-v)^{-1}$ sums the $v$ coefficients, an $u$ just accounts for the shift from $m$ to $m+1$.
It follows that $f_m(u,v) = \dfrac{u^m}{(1-v)^{m+1}}$. If you now sum over $m$, you will get that
$$f(u,v) = \sum_{m\geqslant 0} f_m(u,v) = \frac 1{1-v}\frac{1}{1-\frac{u}{1-v}} = \frac 1{1-u-v}.$$
Expanding now as geometric series in $u+v$, you will recognize that
$$f(u,v) = \sum_{N\geqslant 0} (u+v)^N = \sum_{N\geqslant 0} \binom{N}j u^j v^{N-j} = \sum_{m,n\geqslant 0}\binom{m+n}n u^m v^n$$
giving you the answer.
A: Proposition: $$S_m\left(n\right) = \dfrac{\left(n + m - 1\right)!} {m! \left(n - 1\right)!} = \dfrac{\left(n + m - 1\right) \left(n + m -2\right) \cdots n} {m!}.$$ for $m \ge 0$, $n \ge 1$.
Proof: for $m = 0$, $$S_m\left(n\right) = S_0\left(n\right) = \dfrac{\left(n - 1\right)!} {\left(n - 1\right)!} = 1.$$
For $m > 0$, $$
\begin{array}{rl}
S_{m + 1}\left(n + 1\right) - S_{m + 1}\left( n \right) &= \dfrac{\left(n + m + 1\right)!} {\left(m + 1\right)! n!} - \dfrac{\left(n + m\right)!} {\left(m + 1\right)! \left(n - 1\right)!} \\
& = \dfrac{\left(n + m + 1\right)! - \left( n + m \right)!\cdot n} {(m + 1)! n!} \\
& = \dfrac{\left(n + m\right)!} {m! n!} \\
& = S_m \left(n + 1\right).
\end{array}
$$
Then we have $$ 
\begin{array}{rl}
S_{m + 1}\left(n + 1\right) & = S_{m}\left(n + 1\right) + S_{m + 1}\left(n\right) \\
& = S_{m}\left(n + 1\right) + S_{m}\left(n\right) + S_{m + 1}\left(n - 1\right) \\
& = S_{m}\left(n + 1\right) + S_{m}\left(n\right) + S_{m}\left(n - 1\right) + S_{m + 1}\left(n - 2\right) \\
& = \cdots \\
& = \sum_{k = 1}^{n + 1} S_m\left( k \right).
\end{array}
$$
Therefore, $$S_m\left(n\right) = \dfrac{\left(n + m - 1\right)!} {m! \left(n - 1\right)!}$$ is the solution. To prove it's the only solution, you can assume there is another solution $S_m^\prime\left( n \right)$, and prove by induction that $S_m^\prime\left( n \right) - S_m\left( n \right) = 0$ for $m \ge 0$ and $n \ge 1$.

You are actually not too far from the answer. You already have $$S_2 \left( n \right) = \dfrac{n \left(n + 1\right)} {2}.$$ Then you easily get $$S_3 \left( n \right) = \dfrac{n \left(n + 1\right) \left(n + 2\right)}{2 \times 3}. $$ Here starts the pattern, and you simply prove it.
