Using binomial theorem to calculate nth term of Fibonacci Sequence

Question

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?

Answer 1

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.

Answer 2

Your sum would be equivalent to: \begin{equation} c_k = \sum_{i=0}^{\lfloor k/2 \rfloor} \binom{k-i}{i}. \end{equation} Another way to interpret this would be as the number of ways to express $k$ as an ordered sum of 1's and 2's. To see this, if the sum has $k-2i$ 1's and $i$ 2's, then it has $k-i$ total terms, and then you choose $i$ of them to be 2.

From this, it should be easy to see why $(c_k)$ satisfies the recurrence relation of Fibonacci numbers: there are $c_{k-1}$ sums ending with a 1 and $c_{k-2}$ sums ending with a 2. Then, once you verify $c_0 = c_1 = 1$, you can conclude by induction that $c_k = F_{k+1}$ (reflecting the shift from the $z$ term outside your sum).

[Of course, as another answer indicates, your derivation combined with a more standard solution to the original problem provides another way to derive the identity you were asking for.]