# Recurrence $a_{n}=a_{\lfloor 2n/3\rfloor}+a_{\lfloor n/3\rfloor}$

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.

• See this – Don Thousand Dec 24 '18 at 22:50
• 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.) – Greg Martin Dec 25 '18 at 0:12
• oeis.org/A163867, and yes, the graph is ugly indeed. – Ivan Neretin Dec 25 '18 at 9:04

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