Finding a closed form expression for the recursion $S(n)=\sum\limits_{i=1}^{n-1} iS(i)$ for $n>1$

Question

What is a closed form expression for the sequence $S:\mathbb{N} \rightarrow \mathbb{N}$ such that $S(1)=1$ and $S(n)=\sum\limits_{i=1}^{n-1}iS(i)$ for $n>1$?

I don't know how to approach this problem.

Answer 1

As a general rule, when you have a recurrence $S(n)$ that is a summation of itself, it usually helps to try $S(n)-S(n-1)$ so you can cancel out most of the summation.

$S(n)=\sum\limits_{i=1}^{n-1}iS(i)$

$S(n)-S(n-1)=\sum\limits_{i=1}^{n-1}iS(i) - \sum\limits_{i=1}^{n-2}iS(i) = (n-1)S(n-1)$

Now we are dealing with the recurrence $S(n) - S(n-1) = (n-1)S(n-1)$ which is a little easier to work with. Add $S(n-1)$ to both sides:

$S(n) = nS(n-1)$

And since $S(1) = 1$, we can see that $S(n) = n \cdot (n-1) \cdot (n-2) \cdot \cdots\cdot 2 \cdot 1 = n!$

Answer 2

$S(n)-S(n-1)=\sum_{i=1}^{n-1}iS(i)-\sum_{i=1}^{n-2}iS(i)=(n-1)*S(n-1)$

$S(n)=nS(n-1)$

$S(n)=1*2*\ldots*n=n!$