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

  • $\begingroup$ Generally ordinary generating functions don't play nicely with recurrences defined in terms of floor/ceiling functions. $\endgroup$
    – Math1000
    Jan 30 '20 at 23:01

You should have


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


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


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


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


Working backwards then gives us


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.