I am considering the sequence $$a_n=a_{\lfloor 2n/3\rfloor}+a_{\lfloor n/3\rfloor}$$ with $a_0=1$, and I would like to calculate the limit $$\lim_{n\to\infty} \frac{a_n}{n}$$ I have seen this famous question and its answer, but since the recurrence in this question has only two terms on the RHS instead of three, I was wondering if there is a more elementary solution that does not use specialized knowledge like renewal theory.

I have not made much progress; all I have managed to prove so far is that the sequence contains runs of arbitrarily long length, and this is probably not relevant to the desired limit.

  • $\begingroup$ See this $\endgroup$ – Don Thousand Dec 24 '18 at 22:50
  • 3
    $\begingroup$ Numerical data is consistent with the possibility that $a(n)/n$ is well approximated (as $n$ grows) by $f\big(\frac{\log n}{\log 3}\big)$ for some function $f$ of period $1$—that is, that $a(n)/n$ has some underlying fractal structure. If so, the limit would not exist. (It's also possible, though, that the quotient is more like $\alpha+\varepsilon(n)f\big(\frac{\log n}{\log 3}\big)$ for some function $\varepsilon(n)$ tending to $0$ and some constant $\alpha$ a bit less than $1.2$. But the running averages are also oscillating quite a bit.) $\endgroup$ – Greg Martin Dec 25 '18 at 0:12
  • 3
    $\begingroup$ oeis.org/A163867, and yes, the graph is ugly indeed. $\endgroup$ – Ivan Neretin Dec 25 '18 at 9:04

You can use the Akra-Bazzi theorem (see for instance Leighton "Notes on Better Master Theorems for Divide-and-Conquer Recurrences"; sorry, no "formal" reference available).

Given the recurrence $T(z) = g(z) + \sum_{1 \le k \le n} a_k T(b_k z + h_k(z))$ for $z \le z_0$, with $a_k, b_k$ constants, $a_k > 0$ and $0 < b_k < 1$, if $\lvert h_k(z) \rvert = O(z/\log^2 z)$ and $g(z) = O(z^c)$ for some $c$. Define $p$ as the unique solution to $\sum_{1 \le k \le n} a_k b_k^p = 1$, then the solution to the recurrence satisfies:

$\begin{align*} T(z) &= \Theta\left( z^p \left( 1 + \int_1^n \frac{g(u)}{u^{p + 1}} d u \right) \right) \end{align*}$

In this case the $h_k()$ are at most $1/2$, which satisfies the hypothesis, $g(n) = 0$ and $p = 1$, so we deduce $a_n = \Theta(n)$.


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.