0
$\begingroup$

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

$\endgroup$
1
  • $\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
1
$\begingroup$

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.

$\endgroup$

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.