Before I get started, let me say for complete disclosure this question came up while I was solving a problem from https://projecteuler.net/.

I've been trying to find a non-recursive representation of the following function- $$ S(n) = \sum_{i=1}^{n} \frac{S(n-i)-1}{i!} $$

And I have not been able to find a method that works.
Can anyone help by showing me a method (or an article or anything similar) to solve this type of recurrence relation?

Edit- as pointed out in the comments, the initial value is S(0)=0

Thanks in advance :)

  • $\begingroup$ You need a starting value for $S(0)$. Also, why do you expect there to be a "non-recursive representation"? It's easy to make up random recursions, and almost none of them have simple closed forms. $\endgroup$ – Joe Silverman Sep 9 '15 at 23:30
  • $\begingroup$ If this helps, the generating function is $$ \sum_{n\geqslant0}S(n)x^n=\frac{S(0)+\frac{1-e^x}{1-x}}{2-e^x} $$ $\endgroup$ – მამუკა ჯიბლაძე Sep 10 '15 at 5:33
  • $\begingroup$ How did you get this function? Also, @JoeSilverman you are right, the initial value is S(0)=0. Also, I don't have any proof that this should have a solution, so if you can say it doesn't it also works for me :) $\endgroup$ – mikibest2 Sep 10 '15 at 8:25
  • $\begingroup$ For $f(x)=\sum_nS(n)x^n$ one has $e^xf(x)=\sum_n(\sum_{i\leqslant n}\frac1{i!}S(n-i))x^n$, so your recursion is equivalent to (I am now using $S(0)=0$ to simplify) $f(x)=e^xf(x)-f(x)-(e^x\frac1{1-x}-\frac1{1-x})$. From this,$$f(x)=-\frac1{2-e^x}\frac{e^x-1}{1-x}.$$ $\endgroup$ – მამუკა ჯიბლაძე Sep 10 '15 at 9:29

With $S(0)=0$ one has $$ S(n)=-\sum_{k=1}^n\frac{F_k}{k!} $$ where $F_k$ are the Fubini numbers (also known as ordered Bell numbers). The proof is contained in my comments above, given that the exponential generating function for these numbers is $$ \sum_{n=0}^\infty\frac{F_n}{n!}x^n=\frac1{2-e^x}. $$ There are many different expressions for $F_n$ at the links to OEIS and Wikipedia that I gave, they might be used to obtain some other alternative expressions for $S(n)$; it is difficult to say which ones are more explicit and which ones less.

| cite | improve this answer | |

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.