If we consider $A(x)$ as a generating function of a sequences $a_{n}$, is there any way to find the generating function of, say for example, the sequences : $v_{n}=a_{n}.a_{n+1}$ and $u_{n} = a_{n}^2$ in terms of $A(x)$?
Generating function of $a_{n}^2$ in terms of GF of $a_{n}$?
-
3What you are looking for is the Hadamard product of generating functions. – 2011-09-20
1 Answers
The problem of doing this is equivalent to the problem of finding the Hadamard product $\sum a_n b_n x^n$ of two generating functions $A = \sum a_n x^n$ and $B = \sum b_n x^n$. (The reason is that $a_n b_n = \frac{(a_n + b_n)^2 - a_n^2 - b_n^2}{2}$.)
Hadamard products are difficult to compute in general. However, many classes of generating functions (e.g. the rational ones) are closed under Hadamard product. One way to compute Hadamard products is to consider the integral
$\int_{0}^{2\pi} A(r e^{it}) B(r e^{-it}) \, dt = \int_0^{2\pi} \sum_{m,n} a_n b_m r^{n+m} e^{i(n-m)t} \, dt = 2\pi \sum_{n \ge 0} a_n b_n r^{2n}$
provided that everything converges. If $A, B$ are sufficiently nice functions this integral may be computed in various ways, e.g. using complex analysis. See this blog post for details; there I consider a more general problem, that of computing the diagonal $\sum a_{n,n} x^n$ of a two-variable generating function $A = \sum_{m,n} a_{m,n} x^m y^n$.
-
0@orlp: yes, but it’s pretty annoying. For rational functions there are easier things to do. – 2017-11-14