Generating Function for the square of a sequence

Question

Given any sequence $a_n$ and its generating function $A(x)$, how do I determine the generating function of $a_n^2$?

Or more generally, can the generating function for $a_n^k$ be determined for any $k\in{\mathbb{R}}$?

Thanks for the assistance.

Answer 1

It doesn't seem there is a given way to do this. For example, if there were always some polynomial $P$ such that $P(A(x))$ is the desired generating function, then let $a_n = (-1)^{n+1}/n$ defined on $n \geq 1$. Then

$$A(x) = x - \frac{x^2}{2} + \frac{x^3}{3} - \ldots = \ln(1+x)$$

But squaring the coefficients gives us

$$P(A(x)) = x + \frac{x^2}{4} + \frac{x^3}{9} + \ldots = P(\ln(1+x))$$

When $x=1$, we get $$P(\ln(2)) = \frac{\pi^2}{6}$$

Very strange... It is very unlikely they are not algebraically independent.

Answer 2

Let $$ \eqalign{A(x) &= \sum_{n=0}^\infty a_n x^n \cr B(x) &= \sum_{n=0}^\infty a_n^2 x^n}$$ If the series for $A(x)$ has radius of convergence $R$, $B(x)$ has radius of convergence $R^2$.

In general there is no simple formula for $B$ in terms of $A$. However, if $A(x)$ is a rational function, then so is $B$, and each pole of $B(x)$ is the product of two (not necessarily distinct) poles of $A(x)$.

Answer 3

One trick is to employ following identity of contour integral over the unit circle.

$$\frac{1}{2\pi i}\oint_{|z|=1} z^{m-n} \frac{dz}{z} = \begin{cases} 1, & m = n \\ 0, & m \ne n\end{cases}\quad\text{ for }m,n \in \mathbb{Z}$$

Let's say $A(t)$ and $B(t)$ are OGF (ordinary generating functions) for sequences $(a_0,a_1,\ldots)$ and $(b_0,b_1,\ldots)$. The OGF for the sequence $(a_0b_0, a_1b_1,\ldots)$ will be given by the formula:

$$\begin{cases} A(t) = \sum_{k=0}^\infty a_k t^k,\\ B(t) = \sum_{k=0}^\infty b_k t^k \end{cases} \quad\longrightarrow\quad \sum_{k=0}^\infty a_kb_k t^k = \frac{1}{2\pi i}\oint_{|z|=1} A(\sqrt{t}z)B(\sqrt{t}z^{-1}) \frac{dz}{z}$$

As an example, consider the sequence $(a_0,a_1,\ldots ) = (b_0,b_1,\dots) = (1,2,\ldots)$, we have

$$A(t) = B(t) = \sum_{k=0}^\infty (k+1)t^k = \frac{1}{(1-t)^2}$$

The corresponding contour integral give us

$$\begin{align} & \frac{1}{2\pi i}\oint_{|z|=1} \frac{dz}{z(1-\sqrt{t}z)^2(1-\sqrt{t}z^{-1})^2} = \frac{1}{2\pi i}\oint_{|z|=1} \frac{zdz}{(1-\sqrt{t}z)^2(z-\sqrt{t})^2} \\ = & \left.\frac{d}{dz}\frac{z}{(1-\sqrt{t}z)^2}\right|_{z=\sqrt{t}} = \left.\frac{1+\sqrt{t}z}{(1-\sqrt{t}z)^3}\right|_{z=\sqrt{t}} = \frac{1+t}{(1-t)^3} = \frac{2}{(1-t)^3} - \frac{1}{(1-t)^2}\\ = & \sum_{k=0}^\infty ((k+2)(k+1) - (k+1)) t^k = \sum_{k=0}^\infty (k+1)^2 t^k = \sum_{k=0}^\infty a_k^2 t^k \end{align} $$ Reproducing the OGF for the product sequence.

For more details, look at wiki entry for Generating function transformation. In particular, the part about Hadamard products and refs there.