Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
    
Can you specify what you mean by "relationship"? –  Qiaochu Yuan Nov 5 '09 at 23:26
add comment

5 Answers

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.

share|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.