Coefficient of the generating function $G(z)=\frac{1}{1-z-z^2-z^3-z^4}$

Question

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?

Answer 1

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}

Answer 2

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$.

Answer 3

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$).

Answer 4

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*}