<s>[INST] Coefficient of the generating function $G(z)=\frac{1}{1-z-z^2-z^3-z^4}$ I am seeking the coefficient $a_n$ of the generating function
$$G(z)=\sum_{k\geq 0} a_k z^k = \frac{1}{1-z-z^2-z^3-z^4}$$
The combinatorial background of this question is to solve the recurrence 
$$a_n=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4},\qquad (a_0,a_1,a_2,a_3)=(1,1,2,4).$$
My first idea was to use that $\frac{1}{1-x}=1+x+x^2+...$ which after some expansion leads to
$$a_n = \sum_{k_1+2k_2+3k_3+4k_4 = n}\binom{k_1+k_2+k_3+k_4}{k_1}\binom{k_2+k_3+k_4}{k_2}\binom{k_3+k_4}{k_3}$$
At this point I have no idea how to continue. Looking for a recurrence for $a_n$ would mean to run in circles. I feel that another combinatorial technique is needed, which I dont know. Any ideas?
 [/INST] Let $\left\{z_i\right\}_{i=1}^4$ be the roots of the polynomial in the denominator. Note that:
\begin{eqnarray}
\frac{1}{1-z-z^2-z^3-z^4} = \frac{-1}{\prod\limits_{i=1}^4 (z-z_i)} = 
\sum\limits_{p=1}^4 \frac{-1}{z-z_p} \cdot \left(\prod\limits_{q\neq p} \frac{1}{z_p-z_q}\right)
\end{eqnarray}
Now clearly :
\begin{equation}
a_k = \frac{1}{k!} \frac{d^k}{d z^k}\left. \left(  \frac{1}{1-\sum\limits_{j=1}^4 z^j} \right) \right|_{z=0} =
\sum\limits_{p=1}^4 \frac{1}{z_p^{k+1}} \cdot \left(\prod\limits_{q\neq p} \frac{1}{z_p-z_q}\right) = \left(1,1,2,4,8,15,29,56,108,208,401,\cdots\right)
\end{equation}
</s>