# Solve recursion relation finding closed formula

We have a recursion relation, that looks like:

$$S(1) = 1$$ $$S(n) = \sum_{i=1}^{n-1} i* S(i)$$ with $$n>1$$

Now, I have to solve this relation, finding a closed formular.

I put some values into this relation.

$S(2) = 1$, $S(3) = 3$, $S(4) = 12$ and $S(5) = 60$

I can see, that there is a "system", taking the result from the previous one and multiply it with n. I would say, you can simplify it to $$S(n) = S(n-1) \cdot n$$ For $n = 5$ you have to calculate $S(4)$, which is $12$ and $12\cdot 5 = 60$, that's it.

The problem is, using the simplified version there is still the recursion. My goal is to find a closed formular and prove the equality using induction.

How can I find a closed formula? I could need a hint, please.

• $n!/2$ for $n\ge 2$. – amsmath Oct 17 '17 at 17:46
• @amsmath how have you come to this? Can you tell me your way of thinking? – Blnpwr Oct 17 '17 at 17:47
• Because $n! = (n-1)!\cdot n$. – amsmath Oct 17 '17 at 17:48
• @amsmath oh, I missed that completely. Thank you very much! – Blnpwr Oct 17 '17 at 17:49

$S(n) = \frac{n!}2$ for $n\ge 2$. You can prove that very easily by induction.