Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
I've edited $[]$ to $\lfloor \rfloor$; I hope you don't mind. Nice problem. –  Goos Sep 9 '13 at 2:09
1  
"It is said...." Who said that? –  Jonas Meyer Sep 9 '13 at 2:12
2  
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 '13 at 2:16
1  
@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 '13 at 3:18
2  

3 Answers 3

up vote 37 down vote accepted
+25

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.

share|improve this answer
    
The third equation from (1) should contain $n$ in the summation. Anyway, this is very nice. (+1) –  i707107 Dec 19 '13 at 8:06
    
Thanks. I fixed the equation. –  George Lowther Dec 22 '13 at 12:22

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!

share|improve this answer
    
What is the technique used to find the value of the limit exactly? Could you elucidate a little here? –  Bennett Gardiner Sep 9 '13 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 '13 at 2:22
2  
@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 '13 at 2:22

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.