My rejected !!con 2017 proposal was about how one can calculate a simple closed form solution for the $n$-th Fibonacci number involving exponentiation of the Golden ratio $\varphi$. The approach I used in the proposal is based on writing out a state-space representation for the recurrence and diagonalizing the matrix $\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}$. While this approach is nice because it uses core linear algebra concepts, it is arguably overkill for this problem. Furthermore, it is probably too ambitious for ten minutes.

It turns out there is a much simpler approach using generating functions. Perhaps this was the main objection of the reviewer, that I was not using this elegant formalism! I shall try again next year with this approach and see what happens. This post goes over Section 1.3 of the linked book in slightly more detail.

We start by setting notation. Define the Fibonacci sequence $\{a_n\}_{n=0}^{\infty}$ with the recurrence $$ a_{n} = a_{n-1} + a_{n-2} \:, \:\: a_0 = 0 \:, \:\: a_1 = 1 \:. $$ Let $A(z) = \sum_{k = 0}^{\infty} a_k z^k$ denote the generating function of the $a_n$'s. Our goal is to compute an explicit formula for $A(z)$. We do this by exploiting the definition of the sequence. Specifically, $$ \begin{align*} A(z) &= a_0 + a_1 z + \sum_{k=2}^{\infty} a_k z^k \\ &= z + \sum_{k=2}^{\infty} (a_{k-1} + a_{k-2}) z^k \\ &= z + z \sum_{k=2}^{\infty} a_{k-1} z^{k-1} + z^2 \sum_{k=2}^{\infty} a_{k-2} z^{k-2} \\ &= z + z (A(z) - a_0) + z^2 A(z) \\ &= z + z A(z) + z^2 A(z) \:. \end{align*} $$ Rearranging, we conclude that $$ A(z) = \frac{z}{1 - z - z^2} \:. $$ Now comes the fun part. What is the series expansion for $A(z)$? We first observe that $1 - z - z^2 = (1 - z \varphi_+)(1 - z \varphi_-)$, where $$ \varphi_+ = \frac{1+\sqrt{5}}{2} \:, \:\: \varphi_- = \frac{1-\sqrt{5}}{2} \:. $$ Therefore, $$ \begin{align*} \frac{z}{1-z-z^2} = \frac{z}{(1-z\varphi_+)(1-z\varphi_-)} \:. \end{align*} $$ Now we perform partial fraction decomposition (if you have ever taken an introductory control theory or signal processing course, you will probably remember doing this a lot!). Specifically, we solve for an $A,B$ such that $$ \frac{z}{(1-z\varphi_+)(1-z\varphi_-)} = \frac{A}{1 - z\varphi_+} + \frac{B}{1 - z\varphi_-} \:. $$ This is done by equating $$ z = A(1 - z\varphi_-) + B(1 - z\varphi_+) \:, $$ which gives rise to the two constraints $$ A + B = 0 \:, \:\: A \varphi_- + B \varphi_+ = -1 \:. $$ From this we conclude $$ A = \frac{1}{\varphi_+ - \varphi_-} \:, \:\: B = -\frac{1}{\varphi_+ - \varphi_-} \:. $$ Hence, $$ \frac{z}{(1-z\varphi_+)(1-z\varphi_-)} = \frac{1}{\varphi_+ - \varphi_-} \left( \frac{1}{1-z\varphi_+} - \frac{1}{1-z\varphi_-} \right) = \frac{1}{\sqrt{5}} \left( \frac{1}{1-z\varphi_+} - \frac{1}{1-z\varphi_-} \right) \:. $$ Now, for $|z| < 1/\varphi_+$, $$ \sum_{k=0}^{\infty} \varphi_+^k z^k = \frac{1}{1-z\varphi_+} \:, \:\: \sum_{k=0}^{\infty} \varphi_-^k z^k = \frac{1}{1-z\varphi_-} \:. $$ Hence in this region of convergence, $$ A(z) = \frac{1}{\sqrt{5}} \sum_{k=0}^{\infty} (\varphi_+^k - \varphi_-^k) z^k \:. $$ From this we finally conclude the desired expression for $a_n$, $$ a_n = \frac{1}{\sqrt{5}} (\varphi_+^n - \varphi_-^n) \:. $$