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.
 A: The sequence $a_n/n$ is convergent.
We adapt the idea given in this paper A master theorem for discrete divide and conquer recurrences by Michael Drmota, Wojciech  Szpankowski.
The general theorem and proof are given in the paper, so I will focus on this specific sequence in this posting.
Two main theorems are
Theorem 1 (Landau)

Let $F(s)=\sum a_n n^{-s}$ be a Dirichlet series with a finite abscissa of convergence $\sigma_c$. If $a_n\geq 0$ for all $n$ then the point $\sigma_c$ is a singularity of the function $F(s)$.

Note that if $a_n\geq 0$ for all $n$ then $\sigma_c=\sigma_a$.
Theorem 2 (Wiener-Ikehara)

Let $F(s)=\sum a_n n^{-s}$ with $a_n\geq 0$ for all $n$. Suppose $F(s)$ converges for $\sigma>1$ and $F(s)-c/(s-1)$ extends to a continuous function in the closed half-plane $\sigma \geq 1$. Then
$$
\sum_{n\leq x}a_n=cx+o(x).
$$

Both theorems are in "Multiplicative Number Theory I. Classical Theory, by Montgomery & Vaughan". They are Theorem 1.7 and Corollary 8.8 in the book.
Solution to the problem
Let $b_n=a_n-a_{n-1}$, we have $b_1=1$ and
$$
b_n= {\bf 1}_{3|n} b_{2n/3} + {\bf 1}_{n\equiv 2(3)} b_{(2n-1)/3} + {\bf 1}_{3|n} b_{n/3} \text{ if } n>1. \ (1)
$$
By induction, we have $0\leq b_n\leq n$ for all $n$. Thus, the Dirichlet series $F(s)=\sum b_n n^{-s}$ has a finite abscissa of absolute convergence $\sigma_a$.
By (1), we have for $\sigma>\sigma_a$,
$$
\sum b_n n^{-s} = 1+\sum_{3|n} b_{2n/3} n^{-s} + \sum_k b_{2k-1} (3k-1)^{-s} + \sum_{3|n} b_{n/3} n^{-s}. 
$$
Then
$$
\begin{align}
(1-3^{-s})& \sum b_n n^{-s} = 1 + \sum_k b_{2k} (3k)^{-s} + \sum_k b_{2k-1} (3k-1)^{-s}\\
&=1+(3/2)^{-s} \left( \sum_k b_{2k} (2k)^{-s} + \sum_k b_{2k-1} (2k-\frac23)^{-s} \right).
\end{align}
$$
The last sum can be written as
$$
\sum_k b_{2k-1}(2k-1)^{-s} + \sum_k b_{2k-1}\left((2k-\frac23)^{-s}-(2k-1)^{-s}\right).
$$
Then we have
$$
\left(1-3^{-s}-(\frac32)^{-s}\right) \sum b_n n^{-s} $$
$$= 1+ (\frac32)^{-s} \sum_k b_{2k-1} \left((2k-\frac23)^{-s}-(2k-1)^{-s}\right).  \ \ (2)
$$
By ML-inequality,
$$\left|(2k-\frac23)^{-s}-(2k-1)^{-s}\right|$$
$$=\left|\int_{2k-1}^{2k-\frac23} (-s)x^{-s-1} dx\right|=O(|s|k^{-\sigma-1})$$
with an absolute implied O-constant.
Thus, the RHS of (2) defines an analytic function on $\sigma>\sigma_a-1$. On the LHS of (2), $1-3^{-s}-(3/2)^{-s}$ has a unique real zero at $s=1$ which is simple, and $\sum b_n n^{-s}$ is analytic on $\sigma>\sigma_a$ with singularity at $\sigma_a$ by Landau's theorem. Hence, the singularity at $\sigma_a$ must be removable. This implies $\sigma_a = 1$. Also, $1-3^{-s}-(3/2)^{-s}$ does not have complex zero $1+it$ with $t\neq 0$.
Thus, we obtain the expression
$$
F(s)=\frac{1+ (\frac32)^{-s} \sum_k b_{2k-1} \left((2k-\frac23)^{-s}-(2k-1)^{-s}\right)}{1-3^{-s}-(\frac32)^{-s}}. \ \ (3)
$$
Moreover, $F(s)-c/(s-1)$ extends to a continuous function on $\sigma\geq 1$ where $c$ is
$$
c=\frac{3+2\sum_k b_{2k-1} \left( (2k-\frac23)^{-1}-(2k-1)^{-1}\right)}{\log\frac{27}4}.
$$
By Wiener-Ikehara's theorem, we obtain
$$
\sum_{n\leq x} b_n \sim cx. 
$$
For the original problem, we have
$$
\lim_{n\rightarrow\infty}\frac{a_n}n=\frac{3+2\sum_k b_{2k-1} \left( (2k-\frac23)^{-1}-(2k-1)^{-1}\right)}{\log\frac{27}4}.
$$
Remark.
The convergence may be very slow and difficult to observe. However, the convergence is mainly due to the following
$$\frac{\log(2/3)}{\log(1/3)} \notin \mathbb{Q}.$$
A: 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)$.
