How prove this nice limit $\lim\limits_{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.

Answer

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.

Attribution
Source : Link , Question Author : math110 , Answer Author : George Lowther

Leave a Comment