# 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"? Nov 5, 2009 at 23:26
• Which question were you asking, for the one in the title or the one in the edit? It looks like you selected as correct an answer to the one in the edit while there is an answer to the question in the title. If my assessment is correct you should either change which answer you select as correct or change your question to reflect what you’re looking for. There appears to be a mismatch right now that makes this question less valuable (unless I’m misunderstanding something).
– bob
Jun 13 at 3:23

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. Apr 21, 2015 at 23:39
• I wonder what was meant by sigfpe?? Feb 23, 2016 at 10:47
• Some users leave answers or comments and then later delete them. It seems a MathOverflow user with handle sigfpe did so on this posting. A 10k user or moderator might tell you more. Gerhard "Rarely Deletes Answers Or Comments" Paseman, 2016.02.23. Feb 23, 2016 at 19:18
• Do you need the equation? I seems like squaring the $t$ in the original generating function lets you do a change of variable where you double the degree of each monomial, which would leave gaps at each odd-degree monomial, giving zeros for those coefficients as you showed while mapping the original coefficients to the even degree monomials? Is my thinking right?
– bob
Jun 13 at 3:16
• Sigfpe is Dan Piponi. Jul 19 at 13:26

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)=2A$. So, an equation $\Omega(A)=B$ with $B=0$ implies that $A=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$ 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$$ 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(t2). 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.

• This is the correct answer I believe. I don’t think you need the equations used by the other answers (I think they’re trying to answer something other than what OP technically asked?)
– bob
Jun 13 at 3:18