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$?
Best Answer
Hint for the first question: Newton's binomial theorem.
The second comes from comparing the coefficients of the series.