# 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

I'm trying to solve the following problem:

Given generating functions $A(x)$ for sequence $a_0, a_1, a_2,...$ and $B(x)$ for sequence $b_0, b_1, b_2,...$ express the generating function $C(x)$ for sequence $c_0, c_1, c_2,...$ 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.

## 1 Answer

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?

• I think, it's quite complicated for that problem. The thing is, that I'm struggling with getting the right generating function for the sequence $$b_{0}, b_{3}, b{6}, b{9}, ...$$ – Alex Kunare Oct 19 '16 at 0:48
• @AlexKunare, yes, in fact. But you shall add to your statement above "given $B(x)=b_0+b_1x+b_2x^2+\cdots$" , if I understood your question right. If instead you know the expression of the $b$'s as $b(n)$, then you might put $n = 3\left\lfloor {\frac{n}{3}} \right\rfloor + \bmod (n,3) = 3s + \bmod (n,3)$, if $b\left( {n - 3k} \right) = b\left( {3\left( {s - k} \right) + \bmod (n,3)} \right)$ leads to a manageable expression. – G Cab Oct 19 '16 at 10:20