The Fibonacci sequence, one of the most renowned number sequences in mathematics, is named after Leonardo of Pisa, a prominent mathematician of the European Middle Ages. Born in 1170 into the Bonacci family, Leonardo later became known as Fibonacci — a name derived from the Latin phrase Filius Bonacci, meaning "son of Bonacci."

In his book Liber Abaci (1202), he introduced the now-famous Fibonacci sequence:

\[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... \]

This sequence arose from an arithmetic problem about counting rabbit pairs, where each term represents the total number of rabbit pairs in a given month. The pattern is that each term is the sum of the two preceding terms. This means the Fibonacci sequence can be defined recursively as follows:

\[ F_{0} = 1, F_{1} = 1, F_{n} = F_{n-1} + F_{n-2} \text{ for } n \geq 2 \]

It turns out that the Fibonacci sequence also has a closed-form expression, known as Binet's formula. It is given by:

\[ F_{n} = \frac{\phi^{n} - \psi^{n}}{\sqrt{5}}, \]

where:

\[ \phi = \frac{1 + \sqrt{5}}{2}, \quad \psi = \frac{1 - \sqrt{5}}{2}. \]

Here, \(\phi\) and \(\psi\) are the roots of the characteristic equation associated with the Fibonacci recurrence relation. Binet's formula provides an exact value for \(F_{n}\) without requiring recursive computation, beautifully connecting the Fibonacci sequence to algebra and the golden ratio.

For any sequence of numbers, there exists an associated generating function that encodes the sequence into a formal power series. Given a sequence \(\{a_n\}_{n=0}^{\infty}\), the generating function \(G(x)\) is defined as:

\[ G(x) = \sum_{n=0}^{\infty} a_n x^{n} \]

If we change the sequence by adding \(k\) zeros to the left \(\{0, 0, ..., 0, a_{0}, a_{1}, a_{2}, ... \}\), then the new generating function is \(x^{k}G(x) = a_{0} x^{k} + a_{1} x^{k+1} + a_{2} x^{k+2} + ...\).

Recall that the Fibonacci sequence are defined by the recurrence relation

\[ F_{0} = 1, F_{1} = 1, F_{n} = F_{n-1} + F_{n-2} \text{ for } n \geq 2 \]

We begin by defining the generating function for the Fibonacci sequence as the formal power series whose coefficients are the Fibonacci sequence themselves,

\[ F(x) = \sum_{n=0}^{\infty} F_{n} x^{n} \]

When dealing with a recurrence relation like the Fibonacci sequence, where the recurrence starts with two defined initial terms (\(F_{0}\) and \(F_{1}\)), shifting the generating function twice to the right is necessary to properly represent the recurrence algebraically.

We multiply the generating function for the Fibonacci sequence with \(x\) and \(x^{2}\) to shift the terms:

\[ \begin{aligned} F(x) &= \phantom{ \;\; } F_{0} + F_{1} x + F_{2} x^{2} + F_{3} x^{3} + F_{4} x^{4} + F_{5} x^{5} + F_{6} x^{6} + \dots \\ xF(x) &= \phantom{F_{0} x +} F_{0} x + F_{1} x^{2} + F_{2} x^{3} + F_{3} x^{4} + F_{4} x^{5} + F_{5} x^{6} + \dots \\ x^{2}F(x) &= \phantom{F_{0} x + F_{1} x +} F_{0} x^{2} + F_{1} x^{3} + F_{2} x^{4} + F_{3} x^{5} + F_{4} x^{6} + \dots \end{aligned} \]

When we multiply \(F(x)\) by \(x\), it shifts all terms of the sequence to the right by one position:

\[ xF(x) = x\sum_{n=0}^{\infty} F_{n} x^{n} = \sum_{n=0}^{\infty} F_{n} x^{n+1} = \sum_{n=1}^{\infty} F_{n-1} x^{n} \]

When we multiply \(F(x)\) by \(x^{2}\), it shifts all terms of the sequence to the right by two positions:

\[ x^{2}F(x) = x^{2}\sum_{n=0}^{\infty} F_{n} x^{n} = \sum_{n=0}^{\infty} F_{n} x^{n+2} = \sum_{n=2}^{\infty} F_{n-2} x^{n} \]

The initial terms \(F_{0}\) and \(F_{1}\) need to be added explicitly because they are not part of the recurrence relation and subsitute the recurrence relation for \(F_{n}\) into the coefficients of the sum.

\[ \begin{aligned} F(x) &= F_{0} + F_{1} x^{1} + \sum_{n=2}^{\infty} F_{n} x^{n} \\ &= F_{0} + F_{1} x + \sum_{n=2}^{\infty} \left(F_{n-1} + F_{n-2}\right) x^{n} \\ &= F_{0} + F_{1} x + \sum_{n=2}^{\infty} F_{n-1} x^{n} + \sum_{n=2}^{\infty} F_{n-2} x^{n} \\ &= F_{0} + F_{1} x + x\sum_{n=2}^{\infty} F_{n-1} x^{n-1} + x^{2}\sum_{n=2}^{\infty} F_{n-2} x^{n-2} \\ &= F_{0} + F_{1} x + x\left(\sum_{n=0}^{\infty} F_{n} x^{n} - F_{0}\right) + x^{2}\sum_{n=0}^{\infty} F_{n} x^{n} \\ &= F_{0} + F_{1} x + x(F(x) - F_{0}) + x^{2} F(x) \\ &= F_{0} + F_{1} x + x F(x) - F_{0} x + x^{2} F(x) \end{aligned} \]

From the initial conditions \(F_{0} = 0\) and \(F_{1} = 1\), the equation simplifies to:

\[ F(x) = x + x F(x) + x^{2} F(x) \]

Sovling for the generating function, we get:

\[ F(x) = \frac{x}{1 - x - x^{2}} \]

Now that we have found a closed form for the generating function, all that remains is to express this function as a power series. After doing so, we may match its coefficients term-by-term with the corresponding Fibonacci numbers. The roots of the polynomial \(1 − x − x^{2}\) are \(-\phi\) and \(-\psi\), where

\[ \phi = \frac{1 + \sqrt{5}}{2} \]

and

\[ \psi = \frac{1 - \sqrt{5}}{2}, \]

so the polynomial factors as \(1-x-x^{2}=-(x+\phi)(x+\psi)\).

In order to express the generating function as a power series, we will use the partial fraction decomposition to express it in the form

\[ F(x) = -\frac{x}{(x+\phi)(x+\psi)} = \frac{A}{x+\phi} + \frac{B}{x+\psi}, \]

which is equivalent to

\[ -x = A(x+\psi) + B(x+\phi). \]

Letting \(x=-\phi\):

\[ \begin{aligned} -x &= A(x+\psi) + B(x+\phi) \\ -(-\phi) &= A(-\phi+\psi) + B(-\phi+\phi) \\ \phi &= A(-\phi+\psi) \\ A &= \frac{\phi}{\psi-\phi} \end{aligned} \]

Using the fact that \(\psi-\phi=-\sqrt{5}\), we get:

\[ A = -\frac{\phi}{\sqrt{5}}. \]

Letting \(x=-\psi\):

\[ \begin{aligned} -x &= A(x+\psi) + B(x+\phi) \\ -(-\psi) &= A(-\psi+\psi) + B(-\psi+\phi) \\ \psi &= B(-\psi+\phi) \\ B &= \frac{\psi}{\phi-\psi} \end{aligned} \]

Using the fact that \(\phi-\psi=\sqrt{5}\), we get:

\[ B = \frac{\psi}{\sqrt{5}}. \]

Now substitute these values of \(A\) and \(B\) into the partial fraction decomposition and we get:

\[ F(x) = \frac{1}{\sqrt{5}}\left(\frac{\psi}{x+\psi} - \frac{\phi}{x+\phi}\right). \]

Recall that the sum of a geometric series is given by

\[ \frac{1}{1-x} = \sum_{n=0}^{\infty} x^{n}, \]

assuming \(|x| \lt 1\) for convergence.

The roots \(\phi\) and \(\psi\) are conjugates of each other, and they satisfy the product of the roots relationships:

\[ \phi \cdot \psi = -1. \]

Using the fact that \(\phi=-\frac{1}{\psi}\), we can rewrite the first term of the generating function as

\[ \begin{aligned} \frac{\psi}{x+\psi} &= \frac{1}{1+\frac{x}{\psi}} \\ &= \frac{1}{1-\phi x} \\ &= \sum_{n=0}^{\infty} \phi^{n} x^{n}. \end{aligned} \]

Similarly,

\[ \begin{aligned} \frac{\phi}{x+\phi} &= \frac{1}{1+\frac{x}{\phi}} \\ &= \frac{1}{1-\psi x} \\ &= \sum_{n=0}^{\infty} \psi^{n} x^{n}. \end{aligned} \]

so

\[ \begin{aligned} F(x) &= \frac{1}{\sqrt{5}}\left(\frac{\psi}{x+\psi} - \frac{\phi}{x+\phi}\right) \\ &= \frac{1}{\sqrt{5}}\left(\sum_{n=0}^{\infty} \phi^{n} x^{n} - \sum_{n=0}^{\infty} \psi^{n} x^{n}\right) \\ &= \sum_{n=0}^{\infty} \frac{1}{\sqrt{5}} (\phi^{n} - \psi^{n}) x^{n}. \end{aligned} \]

Since the definition of \(F(x)\) was

\[ F(x) = \sum_{n=0}^{\infty} F_{n} x^{n}, \]

we match the coefficients on corresponding powers of \(x\) in these two expressions for \(F(x)\) to finally arrive at the desired closed form for the n-th Fibonacci number,

\[ F_{n} = \frac{1}{\sqrt{5}} (\phi^{n} - \psi^{n}). \]