<s>[INST] Proving $n$-th term formula of Fibonacci sequence using generating function 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.
 [/INST] 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).
</s>