Find a close form expression for $f(x)$

Question

Here is the problem I am currently having trouble with. I have a pretty decent basis on how to do recurrence relations, but the $\frac{1}{n!}$ has got me in a rut. I tried multiplying the right side by $n!$, but I am not sure if that is allowed. Any help will be much appreciated.

Let $\{s_n\}$ be the sequence defined by the following recurrence relation, and let $F(x)$ be the ordinary generating function for this sequence. Find a closed form expression for $F(x)$.

$$s_n − s_{n−1} = \frac{1}{n!} \quad ∀n ≥ 1, \qquad s_0 = 1$$

Answer 1

HINT: Start with your recurrence,

$$s_n=s_{n-1}+\frac1{n!}\;.\tag{1}$$

Note that if we assume that $s_n=0$ for $n<0$, $(1)$ even gives the correct value for $s_0$, since $0!=1$. Multiply $(1)$ by $x^n$ and sum over $n\ge 0$:

$$F(x)=\sum_{n\ge 0}s_{n-1}x^n+\sum_{n\ge 0}\frac{x^n}{n!}\;.$$

Now do the usual thing to express the first summation in terms of $F(x)$, recognize the second summation as a familiar Taylor series, and solve for $F(x)$. I’ve left the result before solving for $F(x)$ in the spoiler-protected box below.

$F(x)=xF(x)+e^x$

Answer 2

We have, as the (1)st formula: $$F(x)=\sum_{n=0}^\infty s_nx^{n}$$

We can also express it as: $$F(x)=\sum_{n=1}^\infty s_{n-1}x^{n-1}$$

Multiplying both sides by $x$ to give the (2)nd formula: $$xF(x)=\sum_{n=1}^\infty s_{n-1}x^n$$

(1)-(2): $$(1-x)F(x)=s_0+\sum_{n=1}^\infty(s_n-s_{n-1})x^n$$

Simplifying: $$(1-x)F(x)=1+\sum_{n=1}^\infty\frac1{n!}x^n$$

Quickly noticing: $$(1-x)F(x)=e^x$$

Answer 3

You are looking for $F(x)=\sum_{n=0}^\infty s_n x^n$. Note that $s_n-s_{n-1}$ is the coefficient of $x^n$ in $F(x)-xF(x)$. Hence we are given that $(1-x)F(x)$ has the series expansion $\sum_{n=0}^\infty\frac1{n!}x^n$. We recognize this as the series for $e^x$. We conclude $F(x)=\frac{e^x}{1-x}$.