Question

Find a compact form for generating function of the sequence 4, 4, 4, 4, 1, 0, 1, 0, 1, 0, 1, 0,

Answer 1

The generating function for this sequence is

$f(x)=4+4x+4x^2+4x^3+x^4+x^6+x^8+\cdots$

assuming the sequence itself is {4, 4, 4, 4, 1, 0, 1, 0, ...} and the 1-0 pattern repeats forever (as opposes to, say four 4s appearing after every four 1-0 pairs). We can make this simpler by "displacing" the odd-degree terms and considering instead the generating function,

$f(x)=3+4x+3x^2+4x^3+\underbrace{(1+x^2+x^4+x^6+x^8+\cdots)}_{g(x)}$

where the coefficients of $g(x)$ follow a much more obvious pattern of alternating 1s and 0s. Let

$g(x)=\displaystyle\sum_{n=0}^\infty a_nx^n$

where $a_n$ is recursively given by

$\begin{cases}a_0=1\\a_1=0\\a_{n+2}=a_n&\text{for }n\ge0\end{cases}$

and explicitly by

$a_n=\dfrac{1+(-1)^n}2$

so that

$g(x)=\displaystyle\sum_{n=0}^\infty\frac{1+(-1)^n}2x^n$

and so

$\boxed{f(x)=3+4x+3x^2+4x^3+\displaystyle\sum_{n=0}^\infty\frac{1+(-1)^n}2x^n}$