# Using generating functions to solve divide-and-conquer recurrences

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

• Generally ordinary generating functions don't play nicely with recurrences defined in terms of floor/ceiling functions. Jan 30, 2020 at 23:01

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.