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_-$?
 A: (First answer was wrong, because I misread $\phi_+$ and $\phi_-.$)
$\frac{1}{1-z-z^2}$ works for $F_0=1,F_1=1.$ The formula starting at $1$ is $$F_k=\frac1{\sqrt5}\left(\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right)$$
Notice the $k+1.$ You get $k$ in the exponents if you start with $F_0=0.$ Then the function would be $\frac z{1-z-z^2}.$
Now the roots of $1-z-z^2=0$ are the inverses of the roots of $z^2-z-1=0.$ So you get:
$$\phi_+^{-1}=\frac{1+\sqrt5}2\\ \phi_-^{-1}=\frac{1-\sqrt5}2$$

It is easier to skip the inverses. Using $$1-z-z^2=\left(1-\frac{1+\sqrt5}2z\right)\left(1-\frac{1-\sqrt5}2 z\right),$$ and doing the partial fractions for:
$$\frac1{1-z-z^2}=\frac{a}{1-\frac{1+\sqrt5}2z}+\frac{b}{1-\frac{1-\sqrt5}2z}.$$

In general, if $f(z)=\frac{p(z)}{q(z)}$ with $p,q$ polynomials, and we want a power series, we factor $q$ in terms of the inverse of the roots of $q$ (assuming $q(0)\neq 0$):
$$q(z)=q(0)(1-a_1z)\cdots (1-a_nz)$$
It’s just easier that way.
If $q(z)=\sum_{i=0}^n c_iz^i$ then the $a_i$ are roots of the polynomial $\sum_{i}c_iz^{n-i}.$
A: 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.
