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.

  • $\begingroup$ see math.stackexchange.com/questions/1133712/… $\endgroup$
    – sku
    Mar 31 '18 at 6:37
  • $\begingroup$ See Example 1 in Section 2.3 of generatingfunctionology: math.upenn.edu/~wilf/gfology2.pdf $\endgroup$
    – awkward
    Mar 31 '18 at 14:41
  • $\begingroup$ 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 $\endgroup$
    – juliandrew
    Mar 31 '18 at 20:51
  • $\begingroup$ As far as I know, solving the Fibonacci recurrence with an exponential generating function inevitably involves a differential equation. $\endgroup$
    – awkward
    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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.