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.

Given $a_0=1$ and:$$a_n=a_{\frac{n}{2}}+a_{\frac{n}{3}}+a_{\frac{n}{6}}$$Find convergence or divergence of $\frac{a_n}{n}$.

Such a weird problem; I don't know how to attack it. I'm also fairly certain I typed it out correctly.

share|improve this question
    
I am told this has to do with stochastic processes and probability theory. I do not actually know if this is the case. –  user27572 Mar 26 '12 at 5:10
1  
How is $\frac{n}{6}$ defined when $n$ isn't a multiple of $6$? –  Steven Stadnicki Mar 26 '12 at 5:26
    
The sequence needs more than just $a_0$ to be well-defined. You need to know beforehand the values of $a_n$ for all $n$ which are not multiples of $6$. –  Antonio Vargas Mar 26 '12 at 5:30
    
@AntonioVargas I think the same thing as well, but I'm writing down the problem exactly as it was given. –  user27572 Mar 26 '12 at 5:34
2  
@user27572, then the problem is silly exactly as it was given. –  Antonio Vargas Mar 26 '12 at 5:36
show 5 more comments

2 Answers 2

On the assumption that the question is really $$a_n=a_{\lfloor\frac{n}2\rfloor}+a_{\lfloor\frac{n}3\rfloor}+a_{\lfloor\frac{n}6\rfloor}$$ starting with $a_0=1$ (otherwise how do you work out $a_1$?), this is OEIS A007731 and was covered by P. Erdos, A. Hildebrand, A. Odlyzko, P. Pudaite and B. Reznick, The asymptotic behavior of a family of sequences, Pacific J. Math., 126 (1987), pp. 227-241.

They showed that $\dfrac{a_n}{n}$ converges to $\dfrac{12}{\log_e 432} \approx 1.97744865$, though the coveregence is very slow: $\frac{a_n}{n}$ is about $1.8430$ when $n=432^5-1$ but about $2.1175$ when $n=432^5$.

share|improve this answer
    
I'm almost certain that this was what my professor meant, although I have the paper right in front of me, and it says otherwise. ಠ_ಠ Very helpful, @Henry , thanks! –  user27572 Mar 26 '12 at 19:24
add comment

Caveat: This answer is concerned with the problem as stated by the OP, that is, with sequence(s) defined by $a_0=1$ and $a_n=a_{n/2}+a_{n/3}+a_{n/6}$ for every $n\geqslant1$ such that the RHS of the equality makes sense.

user27572: Are you absolutely sure that this problem does not have a solution as given?

Absolutely sure. As explained by @Antonio in the comments the initial condition $a_0=1$ is not enough to determine $(a_n)_{n\geqslant0}$ since one needs to choose the value of $a_n$ for every $n$ not a multiple of $6$.

Obviously, each sequence defined by $a_0=1$ and $a_n=\beta n$ for some fixed $\beta$ and for every nonzero $n$, is a solution. For this choice, the sequence $(b_n)_{n\geqslant1}$ defined by $b_n=a_n/n$ is convergent, to $\beta$.

Here is a different, explicit, choice of $a_n$ for $n$ a power of $2$ and for $n$ a power of $3$, which yields a divergent subsequence $(b_n)_n$ when $n$ is restricted to the products of a power of $2$ by a power of $3$, and, a fortiori, a divergent complete sequence $(b_n)_{n\geqslant1}$. Define $$ a_n=r^{i+j}\quad\text{if}\quad n=2^i3^j, $$ for some fixed $r$. A one-line computation shows that this solves the desired recursion as soon as $r$ solves $r^2=2r+1$, hence, for example, for $r=1+\sqrt2$.

Now, $b_n\to+\infty$ when $n\to\infty$ while $n$ is a power of $2$ because $r\gt2$ and $b_n\to0$ when $n\to\infty$ while $n$ is a power of $3$ because $r\lt3$. Furthermore, for every finite positive $\beta$, there exists a sequence $(n_k)_k$ such that every $n_k$ is the product of a power of $2$ by a power of $3$ and such that $b_{n_k}\to\beta$ when $k\to\infty$. Thus, the set of limit points of the sequence $(b_n)_{n}$ when $n$ is restricted to the products of a power of $2$ by a power of $3$ is $[0,+\infty]$.

More generally, $a_n=\beta\cdot\prod\limits_pr_p^{i_p}$ for $n=\prod\limits_pp^{i_p}$, where the products are over the set of primes $p$, yields a solution for every family of weights $(r_p)_p$ such that $r_2r_3=r_2+r_3+1$.

The (admissible) choice $r_p=p$ for every prime $p$ yields $a_n=\beta n$. This is the only case when $(b_n)_{n\geqslant1}$ converges. The (admissible) choice $r_2=r_3=1+\sqrt2$ yields the solution above.

Note: The recursion $a_n=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3\rfloor}+a_{\lfloor n/6\rfloor}$ is a different story...

share|improve this answer
    
I have to conclude that this was not what my professor meant, but nonetheless I was very interested in a question/solution in the general vein of what I thought my professor meant originally. Cool stuff. –  user27572 Mar 26 '12 at 19:28
add comment

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.