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.

  • $\begingroup$ I am told this has to do with stochastic processes and probability theory. I do not actually know if this is the case. $\endgroup$ – user27572 Mar 26 '12 at 5:10
  • 1
    $\begingroup$ How is $\frac{n}{6}$ defined when $n$ isn't a multiple of $6$? $\endgroup$ – Steven Stadnicki Mar 26 '12 at 5:26
  • $\begingroup$ 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$. $\endgroup$ – Antonio Vargas Mar 26 '12 at 5:30
  • 2
    $\begingroup$ @user27572, then the problem is silly exactly as it was given. $\endgroup$ – Antonio Vargas Mar 26 '12 at 5:36
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ 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! $\endgroup$ – 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...

  • $\begingroup$ 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. $\endgroup$ – user27572 Mar 26 '12 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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