Generating Function functional relation

Question

Suppose I have a generating function which I know satisfies the relation $$x = T(x) (1 - x - T(x^2)).$$ Can I say anything about the coefficients? Ideally I would be able to get some kind of closed form relation (but this seems unlikely).

It might be helpful to list the first few terms of the generating function in question. If my calculations aren't wrong then we have that $$T(x) = 0 + x + x^2 + 2x^3 + 3x^4 + 6x^5 + 10x^6 + 20x^7 + 35x^8 + 68x^9 + \cdots$$

This OEIS entry is directly related to what I am looking at: A319436

Answer 1

Let $T(x) = \sum_{k=0}^\infty a_k x^k$. Rearranging as $$T(x) = x + T(x) (x + T(x^2))$$ and taking coefficients of $x^k$ on each side we get $$a_k = [k=1] + a_{k-1} + \sum_{i=0}^k a_{i/2} a_{k-i}$$ or (subst $j=\tfrac i2$ and pull the first term out of the sum), $$(1 - a_0) a_k = [k=1] + a_{k-1} + \sum_{j=1}^{\lfloor k/2 \rfloor} a_{j} a_{k-2j} $$ Obviously it's worth using $a_0 = 0$ to simplify the LHS.

Numerical examination shows that the terms grow exponentially: $a_k \sim 0.244575110512 \times 1.863835591551907^k$. The growth rate doesn't get a hit in the inverse symbolic calculator, so it probably doesn't have an exact expression. I haven't tried it, but I think you should be able to prove some kind of exponential bound by strong induction using the recurrence on the coefficients.

Answer 2

Let $T(x) = \sum_i a_i x^i$ then we get \begin{align} x &= \left( \sum_{i \ge 0} a_i x^i\right) \left(1- x - \sum_{j \ge 0} a_j x^{2j}\right) \\&= \sum_{i \ge 0} a_i x^i - \sum_i a_i x^{i+1} - \sum_{i,j \ge 0} a_i a_j x^{i+2j} \\&= \sum_{i \ge 0} a_i x^i - \sum_{i \ge 0} a_i x^{i+1} - \sum_{k\ge 0} \sum_{\substack{i,j\ge 0\\i+2j=k}} a_i a_j x^k \\&= a_0 + a_0^2 +\sum_{k \ge 1} \left( a_k - a_{k-1} - \sum_{\substack{i,j\ge 0\\i+2j=k}} a_i a_j \right) x^k \end{align} Comparing coefficients we get \begin{align} 0 &= a_0 + a_0^2, \\ 1 &= a_1 - a_0 - a_1a_0, \\ 0 &= a_k - a_{k-1} - \sum_{\substack{i,j\ge 0\\i+2j=k}} a_i a_j \qquad\text{for all $k\ge 2$.} \end{align}

Hence, we obtain $a_0=0$, $a_1=1$ and for $k\ge 2$ the recursive formula $$ a_k = a_{k-1} + \sum_{\substack{0\le i,j< k\\i+2j=k}} a_i a_j $$ which we may also write more explicitly as $$ a_k = a_{k-1} + \sum_{j=1}^{\lfloor k/2\rfloor} a_{k-2j} a_j. $$