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

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.

-
Can you specify what you mean by "relationship"? –  Qiaochu Yuan Nov 5 '09 at 23:26

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.

-
Know this is quite late, but thank you haha. –  user1447 Apr 21 at 23:39

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.

-

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.

-

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)$.

-

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) = a0 + a1 t + a2 t2 + a3 t3 + ...

and

A(t2) = a0 + a1 t2 + a2 t4 + a3 t6 + ...

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

-