The Akra–Bazzi method handles recurrences of the form $$ f(n) = \sum_{l=1}^k a_l f(n/b_l). $$ Does it work when then number of $a \cdot f(n/b)$ is not finite, meaning that we have a sum that depends on our input $n$?

What about this:

$$ f(n) = \sum_{l=1}^{n} f(n/3^l) $$

Can I say that we need to find the $p$ so that

$$ \sum_{j=1}^{n} (\frac{1}{3^j})^p =1,$$

and because $n \rightarrow \infty$ we can say it is an infinite geometric sum? Or because $n$ is our input we can't say that, and the Akra–Bazzi method fails to deal with this kind of stuff? There is no internet site I found that says $k$ (which in Wikipedia is the number of $f(n/b)$) needs to be finite.


Quoting from Wikipedia, the Akra–Bazzi method applies to recurrences of the form $$ T(x) = g(x) + \sum_{i=1}^k a_i T(b_i x + h_i(x)) $$ where $a_i,b_i$ are constant, $a_i>0$, $0<b_i<1$, $g$ is polynomially bounded, and $h$ is "sublinear enough".

Your recurrence is not of this form, so you cannot apply the Akra–Bazzi method. It could be that the techniques used to prove the Akra–Bazzi theorem also apply to your case, but you will have to look at the proof.

Notice that $$ f(n) - f(n/3) = \sum_{i=1}^{\log_3 n} f(n/3^i) - \sum_{i=1}^{\log_3 (n/3)} f(n/3^{i+1}) = f(n/3), $$ and so $f$ satisfies the recurrence $$ f(n) = 2f(n/3). $$ In particular, $$ f(n) = 2^{\log_3 n} f(1) = n^{\log_3 2} f(1). $$ (Throughout, we are assuming that $n = 3^k$.)

  • $\begingroup$ Taking $n = 3$ as an example, $n/3^n = 1/9$. Is $f$ defined on $1/9$? Is $1/9$ a valid number of inputs? $\endgroup$ – Yuval Filmus Feb 17 at 12:32
  • $\begingroup$ This gives the same result as if we were using the Akra-Bazzi method with $p$ the number such that $\sum_{k=1}^{\infty}(1/3^k)^p=1$, so there might be some hope of generalizing the proof to cases like these. $\endgroup$ – Tassle Feb 17 at 18:37
  • $\begingroup$ Definitely, but it probably requires some nontrivial work. $\endgroup$ – Yuval Filmus Feb 17 at 19:44
  • $\begingroup$ Hi, thank you so much, I know it is probably late, but could you please explain this step: $$\sum_{i=1}^{\log_3 n} f(n/3^i) - \sum_{i=1}^{\log_3 (n/3)} f(n/3^{i+1}) = f(n/3),$$ how did you get from the sums to only $f(n/3)$ ? I don't really see it happening, but it probably a math thing. Thanks again sir! $\endgroup$ – CSch of x Feb 21 at 1:15
  • $\begingroup$ Write it out for some specific value of $n$ to see what’s going on. $\endgroup$ – Yuval Filmus Feb 21 at 7:02

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.