1
$\begingroup$

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$$

$\endgroup$
1
  • $\begingroup$ Note that in general $(a_0+a_1x+a_2x^2+\cdots)(1+x+x^2+\cdots)=a_0+(a_0+a_1)x+(a_0+a_1+a_2)x^2+\cdots$ $\endgroup$ May 5 '16 at 15:42
4
$\begingroup$

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}$.

$\endgroup$
1
  • $\begingroup$ Thanks, Hagen, This helped a-lot $\endgroup$
    – spatel
    May 5 '16 at 15:37
2
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ @spatel: You’re welcome. $\endgroup$ May 5 '16 at 15:38
2
$\begingroup$

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$$

$\endgroup$
1
  • $\begingroup$ Thanks Kenny this was very helpful $\endgroup$
    – spatel
    May 5 '16 at 15:37

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.