# Applying Akra–Bazzi with an unbounded number of summands

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$$?

$$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, $$g$$ is polynomially bounded, and $$h$$ is "sublinear enough".
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$$.)
• 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? Feb 17, 2021 at 12:32
• 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. Feb 17, 2021 at 18:37
• 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! Feb 21, 2021 at 1:15
• Write it out for some specific value of $n$ to see what’s going on. Feb 21, 2021 at 7:02