1
$\begingroup$

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 :)

Improve this question
$\endgroup$
4
  • $\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
    Commented Sep 9, 2015 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$
    – მამუკა ჯიბლაძე
    Commented Sep 10, 2015 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
    Commented Sep 10, 2015 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$
    – მამუკა ჯიბლაძე
    Commented Sep 10, 2015 at 9:29

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .