Solve the recursion given by $f(n) = 2f(n-1) + \frac{(-1)^n}{n!}$ using generating functions.

Question

Assume that $f(0) = 0, f(1) = -1$.

$g(x)$ is $f(n)$'s generating function, I got to the expression:

$ g(x) = \frac{e^{-x}-1}{1-2x} $

But am now stuck, since I can't find a power series for the function in simple terms. Any ideas?

Answer 1

I think you should have $e^{-x}$ in your formula, not $e^x$.

Now you have $g(x) = (e^{-x}-1) \cdot \frac{1}{1-2x}$. Can you find power series for those both separately? Do you know how to multiply power series?

Answer 2

A simpler solution might be expand the recursion equation here.

$$f(n) = \sum_{i = 1}^{n} 2^{n-i} \frac{(-1)^i}{i!} = 2^n\sum_{i = 1}^{n} 2^{-i} \frac{(-1)^i}{i!}$$