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=\frac{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}`