Generating-functions: is there a relationship between a generating function and the corresponding squared generating function - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T12:02:38Z http://mathoverflow.net/feeds/question/4310 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/4310/generating-functions-is-there-a-relationship-between-a-generating-function-and-t Generating-functions: is there a relationship between a generating function and the corresponding squared generating function gmatt 2009-11-05T23:04:51Z 2012-07-22T22:54:01Z <p>Let's say we have a sequence $T(n)$ with the corresponding generating function</p> <p>$$A(t) = \sum_{n = 0}^\infty T(n) t^n$$</p> <p>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$?</p> <p><strong>Edit:</strong> I'm actually trying to solve for the generating function $A(t)$ in the equation</p> <p>$$A(t) + (1+t)A(t^2) = t/(1-t^2)$$</p> <p>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.</p> http://mathoverflow.net/questions/4310/generating-functions-is-there-a-relationship-between-a-generating-function-and-t/4311#4311 Answer by Michael Lugo for Generating-functions: is there a relationship between a generating function and the corresponding squared generating function Michael Lugo 2009-11-05T23:18:01Z 2009-11-05T23:18:01Z <p>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:</p> <p>A(t) = a<sub>0</sub> + a<sub>1</sub> t + a<sub>2</sub> t<sup>2</sup> + a<sub>3</sub> t<sup>3</sup> + ...</p> <p>and</p> <p>A(t<sup>2</sup>) = a<sub>0</sub> + a<sub>1</sub> t<sup>2</sup> + a<sub>2</sub> t<sup>4</sup> + a<sub>3</sub> t<sup>6</sup> + ...</p> <p>so the coefficient of t<sup>n</sup> in A(t<sup>2</sup>) is the coefficient of t<sup>n/2</sup> in A(t) if n is even, and 0 if n is odd.</p> http://mathoverflow.net/questions/4310/generating-functions-is-there-a-relationship-between-a-generating-function-and-t/4323#4323 Answer by Qiaochu Yuan for Generating-functions: is there a relationship between a generating function and the corresponding squared generating function Qiaochu Yuan 2009-11-06T01:21:54Z 2009-11-06T01:21:54Z <p>Ah, that's a much more specific question. In that case, you should do one of two things:</p> <ul> <li><p>Rewrite the given condition in the form A(t^2) = (something that involves A(t)) and iterate it to see what you get.</p></li> <li><p>Compute the first few terms of the series and guess how they continue, then prove your guess.</p></li> </ul> http://mathoverflow.net/questions/4310/generating-functions-is-there-a-relationship-between-a-generating-function-and-t/4327#4327 Answer by Dan Piponi for Generating-functions: is there a relationship between a generating function and the corresponding squared generating function Dan Piponi 2009-11-06T02:46:43Z 2009-11-06T02:46:43Z <p>I believe you're interested in <a href="http://www2.research.att.com/~njas/sequences/A065359" rel="nofollow">this</a> sequence.</p> <p>I generated the series of coefficients directly from your functional equation in A using a couple of lines of Haskell:</p> <pre><code>sq (a:as) = a : 0 : sq as a2 = sq a a = 0 : 1 : tail (tail (zipWith (-) (cycle [0,1]) (zipWith (+) a2 (0:a2)))) </code></pre> <p>I then looked up the series in the sequence database.</p> http://mathoverflow.net/questions/4310/generating-functions-is-there-a-relationship-between-a-generating-function-and-t/4328#4328 Answer by Kirill Levin for Generating-functions: is there a relationship between a generating function and the corresponding squared generating function Kirill Levin 2009-11-06T03:14:55Z 2012-07-22T22:54:01Z <p>Alright, so on the one side, you have this:</p> <p>$$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}$$</p> <p>On the other side, you have:</p> <p>$$\frac{t}{1-t^{2}}=\sum_{n=0}^{\infty}t^{2n+1}$$</p> <p>Equating the coefficients of $x^{2k}$, you have the relation: $T(2k)+T(k)=0$.</p> <p>Equating the coefficients of $x^{2k+1}$, you have the relation: $T(2k+1)+T(k)=1$.</p> <p>Now you can start computing the coefficients: $T(0)=0$, $T(1)=1$, $T(2)=-1$, $T(3)=0$, etc.</p> <p>sigfpe correctly identified <a href="http://www2.research.att.com/~njas/sequences/A065359" rel="nofollow" title="the sequence">the sequence</a>. You can even see these recurrences mentioned in the formula section.</p> http://mathoverflow.net/questions/4310/generating-functions-is-there-a-relationship-between-a-generating-function-and-t/102899#102899 Answer by Duchamp Gérard H. E. for Generating-functions: is there a relationship between a generating function and the corresponding squared generating function Duchamp Gérard H. E. 2012-07-22T21:54:39Z 2012-07-22T22:04:39Z <p>Well, considering the operator </p> <p>$\Omega(A)=A(t)+(1+t)A(t^2)$</p> <p>one sees that $\Omega(A)[0]=2A[0]$. So, an equation $\Omega(A)=B$ with $B[0]=0$ implies that $A[0]=0$.<br></p> <p>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 <i>topologically nilpotent</i>. 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 </p> <p>\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<br> \end{eqnarray}</p> <p>(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)$. </p>