MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Can you specify what you mean by "relationship"? – Qiaochu Yuan Nov 5 '09 at 23:26
up vote 10 down vote accepted

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


On the other side, you have:


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.

share|cite|improve this answer
Know this is quite late, but thank you haha. – user1447 Apr 21 '15 at 23:39
I wonder what was meant by sigfpe?? – მამუკა ჯიბლაძე Feb 23 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. – Gerhard Paseman Feb 23 at 19:18

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Well, considering the operator


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

share|cite|improve this answer

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 + ...


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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.