# Convergence of $\frac{a_n}{n}$ where $a_0=1$ and $a_n=a_{\frac{n}{2}}+a_{\frac{n}{3}}+a_{\frac{n}{6}}$

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.

-
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
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
@user27572, then the problem is silly exactly as it was given. – Antonio Vargas Mar 26 '12 at 5:36
Alright, so I'm going to work under the assumption that the professor handed out a mistyped question, and everyone except me figured this out. :( In which case, thanks guys! It was still very helpful to understand why this question was demonstrably unsolvable. I believe my professor might've meant $a_n=a_{\lfloor\frac{n}2\rfloor}+a_{\lfloor\frac{n}3\rfloor}+a_{\lfloor\frac{n}6‌​\rfloor}$, as specified by @Henry. – user27572 Mar 26 '12 at 19:23

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$.

-
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

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...

-
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