The generating function for Fib numbers

Question

The generating function for Fibonacci numbers can be written $F(z) = \frac{z}{1-y}$ with $y = z + z^2$. Expanding this in terms of y, we have $F(z) = z\displaystyle\sum_{N\geq0}(z + z^2)^N = \displaystyle\sum_{N\geq0}\displaystyle\sum_k {N \choose k}z^{N + k + 1}.$ How did the left-hand side introduce the right-handside here? Also,

But $F_N$ is simply the coefficient of $z^N$ in this, so we must have $F_N = \displaystyle\sum_k{N - k - 1 \choose k},$ how did $F(z)$ become $F_N$ by way of knowing $F_N$ is simply coefficient of $z^N$?

Answer 1

We consider the generating function of the Fibonacci numbers in the form \begin{align*} \color{blue}{F(z)=\frac{z}{1-z-z^2}=\sum_{k=1}^\infty F_kz^k}\tag{1} \end{align*}

Denoting with $[z^N]$ the coefficient of $z^N$ of a series we obtain from (1) \begin{align*} \color{blue}{F_N}&=[z^N]F(z)=[z^N]\frac{z}{1-\left(z+z^2\right)}\\ &=[z^N]z\sum_{k=0}^\infty\left(z+z^2\right)^k\tag{2}\\ &=[z^{N-1}]\sum_{k=0}^\infty z^k(1+z)^k\tag{3}\\ &=\sum_{k=0}^{N-1}[z^{N-k-1}](1+z)^k\tag{4}\\ &=\sum_{k=0}^{N-1}[z^k](1+z)^{N-k-1}\tag{5}\\ &\,\,\color{blue}{=\sum_{k=0}^{N-1}\binom{N-k-1}{k}}\tag{6} \end{align*} and the claim follows.

Comment:

• In (2) we use the geometric series expansion.

• In (3) we factor out $z^k$ and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (4) we apply again the rule as in (3). We also set the upper limit of the sum to $N-1$ since other index values do not contribute.

• In (5) we change the order of summation $k\to N-1-k$.

• In (6) we select the coefficient of $z^k$.

Answer 2

Hint for the first question: Newton's binomial theorem.

The second comes from comparing the coefficients of the series.

Answer 3

The key idea is that a generating function is a (formal) power series, and if two formal power series are equal then all their terms are equal. To look at a simpler example, consider $f(z)=\frac1{(1-z)^2}$. We can find this series by starting with the series $\frac1{1-z}=\sum_nz^n$ and differentiating with respect to $z$, giving us $\frac1{(1-z)^2}=\sum_nnz^{n-1} = \sum_n (n+1)z^n$. On the other hand, we can find it by taking the product of the series for $\frac1{1-z}$ with itself, giving $\frac1{(1-z)^2}=\sum_n(\sum_{k=0}^nz^kz^{n-k})$ $=\sum_n(\sum_{k=0}^n1)z^n$. Here what we learn is $\sum_{k=0}^n 1=n+1$, which is perhaps not the most revelatory identity, but the exact same principles apply to the Fibonacci series manipulations that you're doing.