Generating-functions: is there a relationship between a generating function and the corresponding squared generating function - MathOverflow

Generating-functions: is there a relationship between a generating function and the corresponding squared generating function

2009-11-05T23:04:51Z

Let's say we have a sequence $T(n)$ with the corresponding generating function

$$A(t) = \sum_{n = 0}^\infty T(n) t^n$$

Is there some relationship between the two functions $A(t)$ and $A(t^2)$? And for that matter is there some generalization for any integer power or $t$?

Edit: I'm actually trying to solve for the generating function $A(t)$ in the equation

$$A(t) + (1+t)A(t^2) = t/(1-t^2)$$

this is what inspired my question. My intuition suggested to me that I should look for some kind of relationship between $A(t^2)$ and $A(t)$, hence the vagueness of my question.

Answer by Michael Lugo for Generating-functions: is there a relationship between a generating function and the corresponding squared generating function

2009-11-05T23:18:01Z

I think what you're looking for is a relationship between the coefficients of A(t) and the coefficients of A(t^2). There is one:

A(t) = a₀ + a₁ t + a₂ t² + a₃ t³ + ...

and

A(t²) = a₀ + a₁ t² + a₂ t⁴ + a₃ t⁶ + ...

so the coefficient of tⁿ in A(t²) is the coefficient of t^n/2 in A(t) if n is even, and 0 if n is odd.

Answer by Qiaochu Yuan for Generating-functions: is there a relationship between a generating function and the corresponding squared generating function

2009-11-06T01:21:54Z

Ah, that's a much more specific question. In that case, you should do one of two things:

Rewrite the given condition in the form A(t^2) = (something that involves A(t)) and iterate it to see what you get.
Compute the first few terms of the series and guess how they continue, then prove your guess.

Answer by Dan Piponi for Generating-functions: is there a relationship between a generating function and the corresponding squared generating function

2009-11-06T02:46:43Z

I believe you're interested in this sequence.

I generated the series of coefficients directly from your functional equation in A using a couple of lines of Haskell:

sq (a:as) = a : 0 : sq as
a2 = sq a
a = 0 : 1 : tail (tail (zipWith (-) (cycle [0,1]) (zipWith (+) a2 (0:a2))))

I then looked up the series in the sequence database.

Answer by Kirill Levin for Generating-functions: is there a relationship between a generating function and the corresponding squared generating function

2009-11-06T03:14:55Z

Alright, so on the one side, you have this:

$$A(t)+(1+t)A(t^{2})=\sum_{n=0}^{\infty}T(n)t^{n}+\sum_{n=0}^{\infty}T(n)t^{2n}+\sum_{n=0}^{\infty}T(n)t^{2n+1}$$

On the other side, you have:

$$\frac{t}{1-t^{2}}=\sum_{n=0}^{\infty}t^{2n+1}$$

Equating the coefficients of $x^{2k}$, you have the relation: $T(2k)+T(k)=0$.

Equating the coefficients of $x^{2k+1}$, you have the relation: $T(2k+1)+T(k)=1$.

Now you can start computing the coefficients: $T(0)=0$, $T(1)=1$, $T(2)=-1$, $T(3)=0$, etc.

sigfpe correctly identified the sequence. You can even see these recurrences mentioned in the formula section.

Answer by Duchamp Gérard H. E. for Generating-functions: is there a relationship between a generating function and the corresponding squared generating function

2012-07-22T21:54:39Z

Well, considering the operator

$\Omega(A)=A(t)+(1+t)A(t^2)$

one sees that $\Omega(A)[0]=2A[0]$. So, an equation $\Omega(A)=B$ with $B[0]=0$ implies that $A[0]=0$.

Now the operator $\Omega$ acts on series with zero constant term as $\Omega=I+N$ with $I$ identity and $N(A)=(1+t)A(t^2)$ which is topologically nilpotent. Then $$ \Omega^{-1}=I-N+N^2-N^3+\ldots $$ In this case $\Omega(A)=B$ (in case $B[0]=0$ which is your case) has only one solution which is

\begin{eqnarray} B-(1+t)B(t^2)+(1+t)(1+t^2)B(t^4)+\ldots +\cr (-1)^{k}\Big((1+t)\ldots (1+t^{2^{k-1}})\Big)B(t^{2^k})+\ldots
\end{eqnarray}

(infinite sum). This is easy to program and gives all asymptotic expansions of equations of type $$ A(t)+(1+t)A(t^2)=B\ ;\ B[0]=0 $$ I tried it for $B(t)=\frac{t}{1-t^2}$ (your question) and $B(t)=sin(t)$.