Fibonacci generating function - quick way to see formula

Question

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_-$?

Answer 1

(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}.$

Answer 2

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.