Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Nice problem:
Let $a_{0}=1$ and $$a_{n}=a_{\left\lfloor n/2\right\rfloor}+a_{\left\lfloor n/3 \right\rfloor}+a_{\left\lfloor n/6\right\rfloor}.$$ Show that
$$\lim_{n\to\infty}\dfrac{a_{n}}{n}=\dfrac{12}{\log{432}},$$
where $\lfloor x \rfloor$ is the largest integer not greater than $x$.
It is said this problem was created by Paul Erdős, and I can't find this problem's solution, does anyone have any nice methods? Thank you.
Here's a probabilistic proof. Let $X_t$ ($t=0,1,\ldots$) be a Markov process on the positive integers with $X_0=1$ and, for each $t\ge0$, $$ X_{t+1}=\begin{cases} 2X_t,&\text{with probability }1/2,\\ 3X_t,&\text{with probability }1/3,\\ 6X_t,&\text{with probability }1/6. \end{cases} $$ If we let $p_t(n)=\mathbb{P}(X_t=n)$ then we see that $$ p_{t+1}(n)=1_{\{2\mid n\}}p_t(n/2)/2+1_{\{3\mid n\}}p_t(n/3)/3+1_{\{6\mid n\}}p_t(n/6)/6. $$ Summing over $t$ gives the probability that $X$ ever visits state $n$. $$ p(n)=\mathbb{E}\left[\sum_t1_{\{X_t=n\}}\right]=\sum_t\mathbb{P}(X_t=n)=\sum_tp_t(n). $$ This satisfies $$ p(n)=\frac121_{\{2\mid n\}}p(n/2)+\frac131_{\{3\mid n\}}p(n/3)+\frac161_{\{6\mid n\}}p(n/6) $$ for $n\gt1$ and $p(1)=1$. Now, let $a_n$ be the sequence defined in the question and set $b_n=a_n-a_{n-1}$. This satisfies $b_1=2$ and $b_n=1_{\{2\mid n\}}b_{n/2}+1_{\{3\mid n\}}b_{n/3}+1_{\{6\mid n\}}b_{n/6}$ for $n > 1$. We then see that $b_n$ satisfies the same initial condition and recurrence relation as $2np(n)$, so $b_n=2np(n)$. Hence, $$ \begin{array}{ccr} \begin{align} \frac{a_N-1}{N}&=\frac2N\sum_{n=1}^Nnp(n)=\frac2N\sum_{n=1}^N\mathbb{E}\left[\sum_tn1_{\{X_t=n\}}\right]\\ &=\frac2N\mathbb{E}\left[\sum_tX_t1_{\{X_t\le N\}}\right]. \end{align}&&{\rm(1)} \end{array} $$ The last equality here is obtained by moving the sum over $n$ inside the expectation and commuting with the integral.
We can compute (1) in the limit as $N\to\infty$ using renewal theory. The random variables $U_t=\log(X_t/X_{t-1})$ are independent and identically distributed with $\mathbb{P}(U_t=\log a)=a^{-1}$ for $a\in\{2,3,6\}$. It has mean $c\equiv\mathbb{E}[U_t]=(\log 432)/6$. In terms of the process $Y_t=U_1+\cdots+U_t$, (1) becomes $$ \frac{a_N}N=2\mathbb{E}\left[\sum_t 1_{\{Y_t-\log N\le0\}}e^{Y_t-\log N}\right]+\frac1N. $$ The renewal theorem says that, in the limit as $\log N\to\infty$, this converges to $$ 2c^{-1}\int_{-\infty}^\infty 1_{\{y\le0\}}e^ydy=\frac2c=\frac{12}{\log 432}. $$ I'm using the version of the renewal theorem stated in Kallenberg, Foundations of Modern Probability (Second Ed.), Theorem 9.20, and also known as the Key Renewal Theorem. The precondition on the distribution of $U_t$ for this to apply (other than integrability) is that its support is not contained in $\alpha\mathbb{Z}$ for any $\alpha$. This is true as the ratios of $\log2,\log3,\log6$ are not all rational.
This is a really beautiful problem!
As there is some discussion in the question/comments/one of the answers about the history of this problem, let me narrate here what I found. I’m making this community-wiki as it is not exactly an answer to the question.
In Mathematics Magazine, which is published five times a year by the Mathematical Association of America, in the November 1982 issue (Vol. 55, No. 5), in the problems section (p. 300), the following (much easier) problem was posed anonymously (or rather, by “Anon, Erewhon-upon-Spanish River”, who seems a prolific contributor) as problem 1158 (I’ve changed the notation slightly):
Set $a_0 = 1$ and for $n \ge 1$, $a_n = a_{\lfloor n/2 \rfloor} + a_{\lfloor n/3 \rfloor}$. Find $\lim_{n\to\infty} a_n/n$.
This is a much easier problem, as $\frac12 + \frac13 \neq 1$. (Hint: try polynomial growth.)
Solutions to this problem 1158 were given in the January 1984 issue (Vol. 57, No. 1)’s Problems section (pp. 49–50), under the title A Pseudo-Fibonacci Limit, where it was solved by a host of people.
One of them was Daniel A. Rawsthorne, Wheaton, Maryland, who in the same section of the same issue (p. 42), proposed the harder problem *1185. The asterisk means that he proposed the problem without supplying a solution himself.
Set $a_0 = 1$ and for $n \ge 1$, $a_n = a_{\lfloor n/2 \rfloor} + a_{\lfloor n/3 \rfloor} + a_{\lfloor n/6 \rfloor}$. Find $\lim_{n\to\infty} a_n/n$.
This is a much harder problem, as we need to determine not just the rate of growth ("linear"), but also the constant proportionality factor.
Solutions were given in the January 1985 issue (Vol. 58, No. 1), in the Problems section (pp. 51–52), under the title A Very Slowly Converging Sequence, by (together) P. Erdős, A. Hildebrand, A. Odlyzko, P. Pudaite, and B. Reznick.
Note that the same page also says:
Also solved by Noam Elkies (student), who used Dirichlet series and the residue theorem; and partially (under the assumption that the limit exists) by Don Coppersmith, who gave the explicit formula $$ a_n = 1 + 2 \sum \frac{(r+s+t)!}{r!s!t!} $$ where the sum is extended over all triples $(r, s, t)$ of nonnegative integers such that $2^r3^s6^t \le n$.
Anyway, in their solution, the authors EHOPR also say
We are writing a paper inspired by this problem and its generalizations.
and give general results, such as the following (I've simplified the numerator a bit):
Suppose $a_0 = 1$, and $a_n = \sum_{i=1}^{s} \lambda_i a_{\lfloor n/m_i \rfloor}$ for $n \ge 1$. Suppose also that not all $m_i$s are (integer) powers of some common integer. Then $$ \lim_{n\to\infty} \frac{a_n}{n^{\tau}} = \frac{ \sum_{i=1}^{s} \lambda_i - 1}{\tau \sum_{i=1}^{s} p_i \log m_i} $$ where $\tau$ is the unique real number satisfying $\sum_{i=1}^{s} \lambda_i / m_i^\tau = 1$, and $p_i = \lambda_i / m_i^\tau$ (assuming $\tau \neq 0$).
So in this case, we have $$ \lim_{n\to\infty} \frac{a_n}{n} = \frac{3 - 1}{\frac12\log2 + \frac13\log 3 + \frac16\log 6} = \frac{12}{\log 432} \approx 1.977 $$ The sequence is OEIS A007731.
For the earlier problem (1158), we have, with $\tau \approx 0.78788$ the solution to $(1/2)^x + (1/3)^x = 1$, $p_1 = \frac1{2^\tau}$, and $p_2 = \frac1{3^\tau} = 1 - p_1$, the ratio $\frac{1}{\tau 2^{-\tau}\log 2 + 3^{-\tau}\log 3} \approx 1.469$, so $$a_n \sim 1.469 n^{0.78788}.$$
The paper they wrote was published as:
P. Erdős, A. Hildebrand, A. Odlyzko, P. Pudaite, and B. Reznick,
The asymptotic behavior of a family of sequences,
Pacific Journal of Mathematics, Vol. 126, No. 2 (1987), pp. 227–241: Link 1 (PDF), Link 2
This is an absolutely incredible problem whose solution can be gotten via Tauberian theorems and convolution. The difficult part is showing existence of the limit. See this old AoPS post here for a discussion of this problem and user "fedja" solution which can be found in two of his posts, one for existence and one for a suggested route of calculation:
https://artofproblemsolving.com/community/c7h28832
PS: This is the first I've heard that this problem was designed by Erdős (though somehow it doesn't surprise me). If someone has a reference, that would be great!
