Consider (for fixed $r$) the following function: $$f(z) = \frac{1}{1-z-z^2-\cdots-z^r} = \frac{1}{1-z\frac{1-z^r}{1-z}}=\sum_{j=0}^\infty\left(z\frac{1-z^r}{1-z}\right)^j$$ (Assume everything is ok with regards to convergence.)
The text I am reading claims that if we were to write $f(z)$ in the form $\sum_{n=0}^\infty A_n z^n$, that $$A_n = \sum_{j,k} (-1)^k \binom{j}{k}\binom{n-rk-1}{j-1}$$
I have no idea where this comes from. Could anyone point me in the right direction? Thanks!
Edit: Also, the text states without explanation that in the case $r=2$, the coefficients are the Fibonnaci numbers:
$$\frac{1}{1-z-z^2} = 1 + z + 2z^2 + 3z^3 + 5z^4 + 8 z^5 + 13 z^6 + \cdots$$
Is this a non-trivial result, or am I just not seeing something?
$$f(z) = \sum_{j=0}^\infty \left( z \frac{1 - z^r}{1-z} \right)^j = \sum_{j=0}^{\infty}z^j \left( \sum_{k=0}^j {j\choose k} (-z^r)^k \right) \left( \sum_{m=0}^{\infty} {m+j-1 \choose j-1}z^m \right)$$
Change the order of summation. Note that in order to get a term of $z^n$, we need $j + rk + m = n$, or that $m= n - rk - j$.
The coefficient of $z^n$ is thus
$$ \sum_{j,k} (-1)^k {j\choose k} {n-rk-1 \choose j-1}$$
Let $g(x)$ be the generating function of the Fibonacci numbers. Then,
$\begin{array}{l l l l l l} g(x) &= 1 &+ x & + 2 x^2 & + 3x^3 & + \ldots \\ xg(x) & = & + x & + x^2 & + 2x^2 & + \ldots \\ x^2 g(x) & = & & + x^2 & + x^3 & + \ldots \\ \hline (1-x-x^2)g(x) & = 1 \\ \end{array}$
Hence, $g(x) = \frac{1}{1-x-x^2}$.
Note: This is with $F_1=1, F_2=2$. Depending on how you want to start your Fibonacci sequence, some people use $g(x) = \frac{x}{1-x-x^2}$ as the generating function instead.