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

$\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$ 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$ 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
    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$ Sep 10, 2015 at 9:29

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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