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

Question

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.

Answer 1

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

Answer 2

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