Expanding $\frac{1}{1-z-z^2}$ to a power series. How would you expand the analytic function $$\frac{1}{1-z-z^2}$$ to a series of the form $$\sum_{k=0}^\infty a_k z^k \, \, ?$$

Three ways:


*

*Write as partial fractions:
$$
\frac{1}{1 - z - z^2}
  = \frac{1}{(1 - \tau z) (1 - \overline{\tau} z)}
  = \frac{\tau}{\sqrt{5} (1 - \tau z)} 
      - \frac{\overline{\tau}}{\sqrt{5} (1 -\overline{\tau} z)}
$$
Here $\tau$ is the positive root of $r^2 - r - 1 = 0$, $\overline{\tau}$ the negative one ($\tau$s are zeros of the denominator $1 - z - z^2$). That is:
\begin{align}
\tau            &= \frac{-1 + \sqrt{5}}{2} \\
\overline{\tau} &= \frac{-1 - \sqrt{5}}{2}
\end{align}
This is a pair of geometric series:
$$
[z^n] \frac{1}{1 - z - z^2}
  = \frac{\tau^{n + 1} - \overline{\tau}^{n + 1}}{\sqrt{5}}
$$

*Expand:
\begin{align}
\frac{1}{1 - z(1 + z)}
  &= \sum_{r \ge 0} z^r (1 + z)^r \\
  &= \sum_{r \ge 0} z^r \sum_{0 \le s \le r} \binom{r}{s} z^s \\
[z^n] \frac{1}{1 - z - z^2}
  &= \sum_{r + s = n} \binom{r}{s} \\
  &= \sum_{0 \le k \le n} \binom{k}{n - k}
\end{align}

*Recognize the generating function of the Fibonacci numbers:
$$
F_0 = 0, F_1 = 1, F_{n + 2} = F_{n + 1} + F_n
$$
gives:
$$
F(z) = \sum_{n \ge 0} F_n z^n = \frac{z}{1 - z - z^2}
$$
so that:
$$
\frac{1}{1 - z - z^2}
  = \frac{F(z) - F_0}{z}
  = \sum_{n \ge 0} F_{n + 1} z^n
$$

