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?
 A: The Fibonacci sequence given by $F_{n}=F_{n-1}+F_{n-2}$ has $\dfrac{z}{1-z-z^2}$ as generating function.
By analogy,
$\dfrac{1}{1-z-z^2-z^3-z^4}$ is related to the recurrence
$
a_{n}=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}
$.
A closed expression for this recurrence involves the roots of ${1+z+z^2+z^3=z^4}$.
The exact expression will depend on the initial values $a_0, a_1, a_2, a_3$.
A: 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}
A: 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*}

A: Following your comments above: once you have the recurrence relation $a_k = a_{k-1}+a_{k-2}+a_{k-3}+a_{k-4}$ and the initial condition $(a_0,a_1,a_2,a_3)=(1,1,2,4)$, then you can solve the system by writing 
$$X_k = \begin{pmatrix}
a_{k}\\
a_{k+1}\\
a_{k+2}\\
a_{k+3}
\end{pmatrix}
$$
and 
$$A = \begin{pmatrix}
0&1&0&0\\
0&0&1&0\\
0&0&0&1\\
1&1&1&1\\
\end{pmatrix}
$$
so that it amounts to solving $$
X_{k+1} = A X_k
$$
with the initial condition
$$
X_0 = \begin{pmatrix}
1\\
1\\
2\\
4
\end{pmatrix}
$$
To do that, first you can diagonalize $A$, to get $A=P^{-1}\Delta P$ for some diagonal matrix $\Delta$; leading to $X_k = P^{-1} \Delta^k P X_0$, which once written out gives a closed-form expression for $X_k$ (and thus $a_k$).
