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?

Here is another variant to extract the coefficients $a_n$ resulting in a different formula.

We obtain
  \begin{align*}
\frac{1}{1-z-z^2-z^3-z^4}&=\frac{1}{1-z(1+z+z^2+z^3)}\\
&=\frac{1}{1-z\frac{1-z^4}{1-z}}\tag{1}\\
&=\frac{1-z}{1-2z+z^5}\\
&=(1-z)\sum_{k=0}^\infty z^k(2-z^4)^k\tag{2}\\
&=(1-z)\sum_{k=0}^\infty z^k\sum_{l=0}^k\binom{l}{k}(-1)^lz^{4l}2^{k-l}\tag{3}
\end{align*}

Comment:


*

*In (1) we use the formula for the finite geometric series.

*In (2) we apply the geometric series expansion.

*In (3) we apply the binomial theorem.

Denoting with $[z^n]$ the coefficient of $z^n$ of a series we obtain from (3) 
  \begin{align*}
[z^n]\sum_{k=0}^\infty &z^k\sum_{l=0}^k\binom{k}{l}(-1)^lz^{4l}2^{k-l}\\
&=\sum_{k=0}^n [z^{n-k}]\sum_{l=0}^k\binom{k}{l}(-1)^lz^{4l}2^{k-l}\tag{4}\\
&=\sum_{k=0}^n[z^k]\sum_{l=0}^{n-k}\binom{n-k}{l}(-1)^lz^{4l}2^{n-k-l}\tag{5}\\
&=\sum_{k=0}^{\lfloor{n/4}\rfloor}[z^{4k}]\sum_{l=0}^{n-4k}\binom{n-4k}{l}(-1)^lz^{4l}2^{n-4k-l}\tag{6}\\
&=\sum_{k=0}^{\lfloor{n/4}\rfloor}\binom{n-4k}{k}(-1)^k2^{n-5k}\tag{7}\\
\end{align*}

Comment:


*

*In (4) we apply the rule $[z^p]z^qA(z)=[z^{p-q}]A(z)$ and set the upper limit of the outer sum to $n$ since the power of $z^{n-k}$ is non-negative.

*In (5) we change the order of summation $k\rightarrow n-k$.

*In (6) we observe that due to the factor $z^{4l}$ only multiples of $4$ contribute to the coefficient of $z^n$.

*In (7) we select the coefficient with $k=l$ accordingly.

Respecting the factor $(1-z)$ in (3) we conclude from (3) and (7) the coefficients $a_n$ of the series $\frac{1}{1-z-z^2-z^3-z^4}$
  are given by
  \begin{align*}
\qquad\qquad\color{blue}{a_n=\sum_{k=0}^{\lfloor{n/4}\rfloor}\left[\binom{n-4k}{k}-\frac{1}{2}\binom{n-4k-1}{k}\right](-1)^k2^{n-5k}}\qquad\qquad 
\color{blue}{n\geq 0}
\end{align*}
In general we have
  \begin{align*}
\qquad\qquad&[z^n]\frac{1}{1-z-z^2-\cdots-z^p}=[z^n]\frac{1-z}{1-2z+z^{p+1}}\\
&\qquad=\sum_{k=0}^{\lfloor{n/p}\rfloor}\left[\binom{n-pk}{k}-\frac{1}{2}\binom{n-pk-1}{k}\right](-1)^k2^{n-(p+1)k}\qquad\ \  n\geq 0
\end{align*}

