# exponential generating function - Fibonacci recurrence relation

I am learning about exponential generating functions from some free tutorials and I recently learned how to use ordinary generating functions to solve the Fibonacci recurrence. I was wondering how can one solve the Fibonacci recurrence using exponential generating functions. I have not seen many examples of recurrences being solved using exponential generating functions so this will be very helpful to me.

Thank you.

• – sku
Mar 31 '18 at 6:37
• See Example 1 in Section 2.3 of generatingfunctionology: math.upenn.edu/~wilf/gfology2.pdf Mar 31 '18 at 14:41
• I have not studied differential equations before so there is part in the example that I am not following. So the author just solves the diff eq and says to apply the operator $[x^n/n!]$. Is there an example w/o diferentialf equations @awkward Mar 31 '18 at 20:51
• As far as I know, solving the Fibonacci recurrence with an exponential generating function inevitably involves a differential equation. Apr 1 '18 at 12:40

$$F_n=\dfrac{1}{\sqrt{5}}\left[\phi^n+\left(1-\phi\right)^n\right]$$, where $$\phi=\dfrac{\sqrt{5}+1}{2}$$ (golden ratio)
$$\quad\sum_{n\ge0} F_n\dfrac{z^n}{n!} \\ =\dfrac{1}{\sqrt{5}}\sum_{n\ge0} \left[\phi^n+\left(1-\phi\right)^n\right]\dfrac{z^n}{n!}\\=\dfrac{1}{\sqrt{5}}\sum_{n\ge0}\left[\dfrac{\left(\phi z\right)^n}{n!}+\dfrac{\left(z-\phi z\right)^n}{n!}\right]\\=\dfrac{1}{\sqrt{5}}\left[e^{z\phi}+e^{z\left(1-\phi\right)}\right]$$
Your recurrence is $$F_{n + 2} = F_{n + 1} + F_n$$ and $$F_0 = 0, F_1 = 1$$. Start by defining $$f(z) = \sum_{n \ge 1} F_n \frac{z^n}{n!}$$, multiply your recurrence by $$z^n/n!$$ and sum over $$n \ge 0$$, recognize some sums:
\begin{align*} \sum_{n \ge 0} F_{n + 2} \frac{z^n}{n!} &= \sum_{n \ge 0} F_{n + 1} \frac{z^n}{n!} + \sum_{n \ge 0} F_n \frac{z^n}{n!} \\ \frac{d^2}{d z^2} f(z) &= \frac{d}{d z} f(z) + f(z) \end{align*}
You get a differential equation, from the initial values you get that $$f(0) = 0$$, $$f'(0) = 1$$.