1

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.

Archisman Panigrahi
  • 2,156
  • 2
  • 19
  • 30
Blnpwr
  • 931

1 Answers1

2

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

amsmath
  • 10,633