Using generating functions to solve divide-and-conquer recurrences

Question

I'm having trouble using generating functions to solve recurrences that arise in analysing divide-and-conquer algorithms. For example, consider the recurrence
$$T_n = T_{\lfloor n/2\rfloor} + T_{\lfloor n/3 \rfloor} + 6$$
If we let $T(x) = \sum_{n\geq 0} T_nx^n$, then we get
\begin{align}
\sum_{n\geq 0} T_nx^n &= \sum_{n\geq0}(T_{\lfloor n/2\rfloor} + T_{\lfloor n/3 \rfloor} + 6)x^n\\
&= (1+x)\sum_{n\geq 0} T_nx^{2n} + (1+x+x^2)\sum_{n\geq0}T_nx^{3n} + 6 \sum_{n\geq0} x^n. \\
\end{align}
This results in the equation
$$T(x) = \frac{(1+x^2)T(x^2) + (1-x^3) T(x^3) + 1}{1-x},$$
which I have no idea how to tackle. Is it possible that ordinary generating functions are just not cut out for this task? Or perhaps I made a mistake somewhere? Any help would be much appreciated! (I understand that the recurrence can be solved in many other ways; I was wondering if it can also be solved using generating functions.)

Answer 1

You should have

$$0=5T(x)+(1+x)T(x^2)+(1+x+x^2)T(x^3)$$

By multiplying both sides by $1-x$ we can get

$$0=5(1-x)T(x)+(1-x^2)T(x^2)+(1-x^3)T(x^3)$$

Let $f(x)=(1-x)T(x)$ to simplify this to

$$0=5f(x)+f(x^2)+f(x^3)$$

Substituting $x\mapsto 2^{-2^x}$ and letting $g(x)=f(2^{-2^x})$ turns this into

$$0=5g(x)+g(x+1)+g(x+\log_2(3))$$

There are non-trivial solutions to this, but supposing we stick to exponential functions this boils down to

$$g(x)=\sum_{0=5+r+r^{\log_2(3)}}a_rr^x$$

Working backwards then gives us

$$f(x)=g(\log_2(-\log_2(x)))=\sum_{0=5+r+r^{\log_2(3)}}a_r[-\log_2(x)]^{\log_2(r)}$$

which at this point one can see there's no hope in deriving the coefficients from here.