<s>[INST] Fibonacci generating function - quick way to see formula I know that
$$
\frac{1}{1-z-z^2} = \sum_{k = 1}^\infty a_nz^n
$$
in $B_{\varepsilon}(0) \subseteq \mathbb{C}$ where $(a_n)_{n \in \mathbb{N}}$ denotes the Fibonacci series and $\varepsilon > 0$ is small. This can be obtained by simply comparing coefficients.
Then I wanted to find the power series in a direct way. So I carried out partial fraction decomposition and used the geometric series. I got
$$
\frac{1}{1-z-z^2} = \sum_{k = 0}^\infty\frac{1}{\sqrt{5}}\left(\varphi_{+}^{-k-1} - \varphi^{-k-1}_-\right)z^k, ~ \quad \varphi_+ := \frac{-1+\sqrt{5}}{2},~\varphi_- := \frac{-1-\sqrt{5}}{2}.
$$
So how can I see quickly confirm the well known explicit Fibonacci-formula, i.e.
$$
\varphi_+^{-k-1} = \left(\frac{1+\sqrt{5}}{2} \right)^{k+1}
$$
for $k \in \mathbb{N}_0$ and the analogue for $\varphi_-$?
 [/INST] Let $\sum_{n=0}^\infty a_n z^n$ be the Macluarin series for $\frac{1}{1 - z - z^2}$. We can easily prove that $a_n$ is the Fibonacci sequence. Note that, for sufficiently small $z$,
\begin{align*}
1 &= (1 - z - z^2)\sum_{n=0}^\infty a_n z^n \\
&= \sum_{n=0}^\infty a_n z^n - \sum_{n=0}^\infty a_n z^{n+1} - \sum_{n=0}^\infty a_n z^{n+2} \\
&= a_0 + a_1 z + \sum_{n=2}^\infty a_n z^n - a_0 z - \sum_{n=1}^\infty a_n z^{n+1} - \sum_{n=0}^\infty a_n z^{n+2} \\
&= a_0 + (a_1 - a_0)z + \sum_{n=0}^\infty a_{n + 2} z^{n + 2} - \sum_{n=0}^\infty a_{n+1} z^{n+2} - \sum_{n=0}^\infty a_n z^{n+2} \\
&= a_0 + (a_1 - a_0)z + \sum_{n=0}^\infty (a_{n + 2} - a_{n+1} - a_n)z^{n + 2}.
\end{align*}
From this, we see $a_0 = 1$, $a_1 - a_0 = 0$, hence $a_1 = 1$, and $a_{n+2} - a_{n+1} - a_n = 0$ for all $n \ge 0$, i.e. $a_n = a_{n-1} + a_{n-2}$, for all $n \ge 2$. This is precisely the (shifted) Fibonacci sequence.
</s>