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*