# How to solve a complex recursive relation

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

• 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. – Joe Silverman Sep 9 '15 at 23:30
• 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}$$ – მამუკა ჯიბლაძე Sep 10 '15 at 5:33
• 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}.$$ – მამუკა ჯიბლაძე 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.