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