Proving $n$-th term formula of Fibonacci sequence using generating function

Question

I am trying to get the formula $F_n = \frac{\phi^n - \psi^n}{\phi - \psi}$ using generating functions. I managed to find that $G_F(x) = \frac{1}{1 - x - x^2}$ then I used partial fraction decomposition to find that $$G_F(x) = \frac{1}{\phi - \psi} \Biggl(\frac{1}{x - \psi} - \frac{1}{x - \phi}\Biggr)$$

After that I took the following steps to simplify: $$G_F(x) = \frac{1}{\phi - \psi} \Biggl(\frac{\frac{1}{\psi}}{\frac{x}{\psi} - 1} - \frac{\frac{1}{\phi}}{\frac{x}{\phi} - 1}\Biggr)$$

$$ = \frac{1}{\phi - \psi} \Biggl(\frac{\psi}{\frac{x}{\phi} - 1} - \frac{\phi}{\frac{x}{\psi} - 1}\Biggr), since\ \psi = -\frac{1}{\phi}$$

$$ = \frac{1}{\phi - \psi} \Biggl(\frac{\psi}{-\psi x - 1} - \frac{\phi}{-\phi x - 1}\Biggr)$$

$$ = \frac{1}{\phi - \psi} \Biggl(\frac{\phi}{\phi x + 1} - \frac{\psi}{\psi x + 1}\Biggr) $$

The issue is that this function generates the series

$$a_n = \frac{\phi \cdot (-\phi)^n - \psi \cdot (-\psi)^n}{\phi - \psi}$$

Now, the $n + 1$ as the exponent is probably due to the fact that I started my series with $1$ instead of $0$.But I don't understand why is my series so close yet false.

Answer 1

Thanks to @halrankard, I found out that I messed up with the sign of the constants here. In my solution, $\phi_{wrong} = -\phi$ and $\psi_{wrong} = -\psi$. Replacing $-\phi$ by $\phi$ and $-\psi$ by $\psi$ in the final formula yields:

$$ F_n = \frac{-\phi * \phi ^ n - (-\psi * \psi ^ n)}{-\phi - (-\psi)} $$ $$ = \frac{\psi ^ {n + 1} - \phi ^ {n + 1}}{\psi - \phi} $$ $$ = \frac{\phi ^ {n + 1} - \psi ^ {n + 1}}{\phi - \psi} $$

Note that the $n + 1$ in the exponent comes from the fact that I ignored the term $F_0 = 0$ when computing my generating function

Answer 2

Another way is to use exponential generating functions. Start with $F_{n + 2} = F_{n + 1} + F_n$, $F_0 = 0, F_1 = 1$. Define:

$\begin{align*} \widehat{F}(z) &= \sum_{n \ge 0} F_n \frac{z^n}{n!} \end{align*}$

Now you see that:

$\begin{align*} \frac{d}{d z} \widehat{F}(z) &= \sum_{n \ge 0} F_{n + 1} \frac{z^n}{n!} \end{align*}$

Take the recurrence, multiply by $z^n / n!$, sum over $n \ge 0$ and recognize the resulting 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} \widehat{F}(z) &= \frac{d}{d z} \widehat{F}(z) + \widehat{F}(z) \end{align*}$

As initial values you know:

$\begin{align*} \widehat{F}(0) &= F_0 = 0 \\ \widehat{F}'(0) &= F_1 = 1 \end{align*}$

The traditional ODE dance tells you:

$\begin{align*} \widehat{F}(z) &= c_1 \exp(\phi z) + c_2 \exp(\psi z) \end{align*}$

Using the initial conditions gets you:

$\begin{align*} F_0 &= 0 = c_1 + c_2 \\ F_1 &= 1 = c_1 \phi + c_2 \psi \end{align*}$

From the first equation we get $c_2 = - c_1$, we also know $\psi = 1 - \phi$:

$\begin{align*} 1 &= c_1 \phi - c_1 (1 - \phi) \\ c_1 &= \frac{1}{2 \phi - 1} \\ &= \frac{1}{\phi - \psi} \\ c_2 &= - \frac{1}{2 \phi - 1} \\ &= \frac{1}{\psi - \phi} \end{align*}$

Extracting coefficients then gives:

$\begin{align*} F_n &= \frac{\phi^n - \psi^n}{\phi - \psi} \end{align*}$

(Not that world-shattering here, but a useful trick if your recurrence has factors $n$ thrown in).