Applying Akra–Bazzi with an unbounded number of summands

Question

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.

Answer 1

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