Express $C(x)$ through $A(x)$ and $B(x)$, where $C(x)$, $A(x)$, $B(x)$, are generating functions of sequences $c_{n}$, $a_{n}$, $b_{n}$ respectively

Question

I'm trying to solve the following problem:

Given generating functions $A(x)$ for sequence $a_0, a_1, a_2, \dots$ and $B(x)$ for sequence $b_0, b_1, b_2, \dots$ express the generating function $C(x)$ for sequence $c_0, c_1, c_2, \dots$ through $A(x)$ and $B(x)$. The $n$-th term for sequence $c_n = \sum_{k=0}^{[n/3]}{a_kb_{n-3k}}$.

I understand that the answer will be some sort of convolution, however, I'm struggling with getting the modified $B(x)$. I think there will something like modulo, but I can't get my head around it.

Thanks in advance.

Answer 1

Consider that, given $$ A(z) = \sum\limits_{n\, \geqslant \,0} {\,a_{\,n} \,z^{\,n} } \;\quad \left| {\;a_{\,n\, < \,0} = 0} \right. $$ then $$ \begin{gathered} \sum\limits_{0\, \leqslant \,k\, \leqslant \,m - 1} {A(\;e^{\,i\,k\frac{{2\,\pi }} {m}} )} = \sum\limits_{n\, \geqslant \,0} {\,a_{\,n} \sum\limits_{0\, \leqslant \,k\, \leqslant \,m - 1} {\left( {e^{\,i\frac{{2k\,\pi }} {m}} } \right)^{\,n} } \,} = \hfill \\ = \sum\limits_{n\, \geqslant \,0} {\,a_{\,n} \sum\limits_{0\, \leqslant \,k\, \leqslant \,m - 1} {\left( {e^{\,i\frac{{2n\,\pi }} {m}} } \right)^{\,k} } \,} = m\,\sum\limits_{n\, \geqslant \,0} {\,a_{\,n\,m} \,} \hfill \\ \end{gathered} $$ and $$ \sum\limits_{0\, \leqslant \,k\, \leqslant \,m - 1} {A(\;z^{\,\frac{1} {m}} \,e^{\,i\,k\frac{{2\,\pi }} {m}} )} = m\,\sum\limits_{n\, \geqslant \,0} {a_{\,n\,m} \,z^{\,n} \,} $$ Can you proceed from here?

Answer 2

Answer is $С(x)= B(x) \cdot A(x^3)$:

$$ (a_0 + a_1 \cdot x^3 + a_2 \cdot x^6 + \ldots) \cdot (b_0 + b_1 \cdot x + b_2 \cdot x^2 + b_3 \cdot x^3 + \ldots) = \\ (a_0 \cdot b_0) + (b_1 \cdot a_0) \cdot x + \;\ldots\;\\ + (b_{10} \cdot a_0 + b_7 \cdot a_1 + b_4 \cdot a_2 + b_1 \cdot a_3) \cdot x^{10} + \ldots. $$

Answer 3

\begin{align} C(x) &= \sum_{n\ge 0} c_n x^n \\ &= \sum_{n\ge 0} \sum_{k=0}^{\lfloor n/3 \rfloor} a_k b_{n-3k} x^n \\ &= \sum_{k\ge 0} a_k x^{3k} \sum_{n\ge 3k} b_{n-3k} x^{n-3k} \\ &= \sum_{k\ge 0} a_k x^{3k} B(x) \\ &= B(x) \sum_{k\ge 0} a_k (x^{3})^k \\ &= B(x) A(x^3) \end{align}