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.

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.