In a Complex Analysis course, I was asked to show that $$f(z) = \frac{z}{1-z-z^2}$$ must have the Fibonacci sequence as the coefficients of its power series, with $f(0) = 0$ and $f(1)=1$. I took an unusual approach and came up with a formulation of the Fibonacci sequence that I can't find anywhere else, although I'm unsure on how to prove that what I have is equivalent to Fibonacci. Consider: $$ \begin{align*} f(z) &= \frac{z}{1-(z^2+z)} \\ &= z \sum\limits_{k=0}^\infty(z+z^2)^k \\ &= z \sum\limits_{k=0}^\infty\sum\limits_{n=0}^k\binom{k}{n}z^{k-n}z^{2n} \\&= z \sum\limits_{k=0}^\infty\sum\limits_{n=0}^k\binom{k}{n}z^{k+n} \end{align*}$$ Expanding this, I realized that the coefficient for each $z^k$ will be the sum of the binomials whose top and bottom sum to $k$. For example, the coefficient for $z^5$ is $$\binom{5}{0} + \binom{4}{1} + \binom{3}{2} = 8 = f(5)$$ How can I prove that this equality holds for all $k$ and what is the relation between the sum of these binomials and the Fibonacci sequence?
[Math] Using binomial theorem to calculate nth term of Fibonacci Sequence
fibonacci-numberspower series
Best Answer
You may assume that $$ f(z)=\frac{z}{1-z-z^2}=\sum_{n\geq 0} a_n z^n \tag{1} $$ where $a_0=f(0)=0$ and $a_1=f'(0)=1$. Since $(1-z-z^2)\,f(z)=z$ and $$ (1-z-z^2)\sum_{n\geq 0}a_n z^n = a_0+(a_1-a_0)z+\sum_{n\geq 2}(a_{n}-a_{n-1}-a_{n-2}) z^n\tag{2}$$ we must have $a_{n+2}=a_{n+1}+a_{n}$ for any $n\geq 0$, hence $a_n=F_n$.
Your derivation shows additionally that $$ F_n = \sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\binom{n-k-1}{k}\tag{3} $$ that is also proved here. Through the identity $$ \frac{z}{1-z-z^2} = \frac{1}{\sqrt{5}}\left(\frac{1}{1-\sigma z}-\frac{1}{1-\bar{\sigma} z}\right)=\sum_{n\geq 0}\frac{\sigma^n-\bar{\sigma}^n}{\sqrt{5}}z^n\tag{4} $$ we also recover the explicit formula for Fibonacci numbers by partial fraction decomposition and geometric series.