Combinatorics: Finding a general solution for a recurrence relation.

Question

Find a general solution for this recurrence relation: $$f(n) = 2f(n-1) + \frac{(-1)^n}{n!}$$ when $f(0) = 0, f(1) = 1$ EDIT: n >= 2

Answer 1

Remark: If $f(0)=0$, then $f(1)$ must be equal to $-1$, not $1$ as claimed. [Just plug $n=1$ in the recursion]

Multiply by $z^n$ and sum over $n\geq 1$ $$ \sum_{n\geq 1}f(n)z^n=2\sum_{n\geq 1}f(n-1)z^n+\sum_{n\geq 1}\frac{(-1)^n}{n!}z^n $$ and define $\sum_{n\geq 0}f(n)z^n=G(z)$. Hence $$ G(z)-f(0)=2zG(z)-e^{-z} \left(e^z-1\right)\ . $$ Using $f(0)=0$, this leads to $$ G(z)=\frac{ 1-e^{-z}}{2z-1}\ . $$ The general term $f(n)$ of the recursion can be obtained from Cauchy's formula. Can you proceed from here?