# How prove this nice limit $\lim_{n\to\infty}\frac{a_{n}}{n}=\frac{12}{\log{432}}$

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.

-
I've edited $[]$ to $\lfloor \rfloor$; I hope you don't mind. Nice problem. –  Goos Sep 9 at 2:09
"It is said...." Who said that? –  Jonas Meyer Sep 9 at 2:12
I fixed up the spelling and grammar in the question, as it's an interesting problem and I think that English is perhaps not your native language :) Hope that's okay. –  Bennett Gardiner Sep 9 at 2:16
@JonasMeyer: Here is the explicit link provided by tian27546 in the forum math110 mentions. http://www.dtc.umn.edu/~odlyzko/doc/arch/sequence.family.pdf –  Prism Sep 9 at 3:18

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_t1_{\{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.

-
The third equation from (1) should contain $n$ in the summation. Anyway, this is very nice. (+1) –  i707107 22 hours ago

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:

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=70&t=28832&hilit=Tauberian

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!

-
What is the technique used to find the value of the limit exactly? Could you elucidate a little here? –  Bennett Gardiner Sep 9 at 2:20
Thank you, This link is prove this limt is exsit,But can't solution this limt value.Thank you –  math110 Sep 9 at 2:22
@Bennett Gardiner: in the link above, scroll down to user "fedja" and the few posts he makes which explain it. One post shows the existence and the other suggests how to calculate it. –  Alex R. Sep 9 at 2:22