# Combinatorics: Finding a general solution for a recurrence relation. [closed]

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

## closed as off-topic by Abcd, Martín Vacas Vignolo, A. Goodier, Paul Frost, José Carlos SantosDec 30 '18 at 15:51

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Abcd, Martín Vacas Vignolo, A. Goodier, Paul Frost, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.

• What have you tried? – MisterRiemann Dec 30 '18 at 11:04
• I have tried to use generating functions, but it just didn't go well... – Robo Yonuomaro Dec 30 '18 at 11:07
• Iz is $$a_n=c_1 2^{n-1}+\frac{2^n \left(\frac{\Gamma \left(n+1,-\frac{1}{2}\right)}{\Gamma (n+1)}-\sqrt{e}\right)}{\sqrt{e}}$$ – Dr. Sonnhard Graubner Dec 30 '18 at 11:12
• @Dr.SonnhardGraubner. This is pure magics ! – Claude Leibovici Dec 30 '18 at 14:25
• Expanding this into an answer would be appreciated. – marty cohen Dec 30 '18 at 14:26

## 1 Answer

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?

• You are right about that, I forgot to mention that n >= 2. How can it be solved with this? – Robo Yonuomaro Dec 30 '18 at 15:57