10
$\begingroup$

I have some problems, with the convergence of this sequence defined recursively. It's clear that it's bounded. But is it convergent? How can I check for convergence?

$ a_0 = a_1 = 1 $

$ a_n = a_{a_{n - 1} } + a_{n - a_{n - 1} } $

How do I prove that the sequence $\frac{a_n}{n}$ converges? I tried but am not able to do it.

  • 2
    @Jineon: the initial conditions, however, are key. If you specify $a_0 = a_1 = 1$, then inductively if $a_n = n$, then $a_{n+1} = a_n + a_{n+1 - n} = n + 1$, showing that $\lim a_k/k = 1$.2011-08-17

2 Answers 2

13

In the interest of teaching a man to fish: Google "Conway's $10,000 sequence". Discover mathworld page. Look at bibliography. Main reference seems to be a 1988 talk by Conway at Bell Labs. Search on youtube, google and the Bell Labs website to see whether that talk has been placed online. If this were a crucial issue, next step would be to figure out who to e-mail at Bell Labs to ask for access, but I didn't do that.

Go back to the Mathworld bibliography and notice the Kubo-Vakil paper.

On Conway's recursive sequence T. Kubo and R. Vakil, Discrete Mathematics, Volume 152, Issues 1-3, 20 May 1996, Pages 225-252

It's in a major journal, its title suggests that it will provide a good survey of known material, and the second author is known for clear exposition.

At this point, my life is easy because my employer (University of Michigan) has a subscription to Discrete Math, so I go download the paper. If this weren't possible, my next steps would be to check the author's webpages (no luck) and then go in person to a nearby university library to see if they subscribe.

Your question is answered in Section 8.3.


EDIT: The following is the Mathscinet review written by Tom Brown:

The recurrence $a(n)=a(a(n−1))+a(n−a(n−1)),a(1)=a(2)=1$ defines an integer sequence, publicized by Conway and Mallows, with amazing combinatorial properties that cry out for explanation. We take a step towards unravelling this mystery by showing that $a(n)$ can (and should) be viewed as a simple `compression' operation on finite sets. This gives a combinatorial characterization of $a(n)$ from which one can read off most of its properties. We prove a conjecture of Mallows on the asymptotic shape of $a(n)$, and give an algorithm for solving Conway's challenge problem about the epsilontics of $(a(n)/n−1/2)$. Along the way we encounter some beautiful constructions involving trees, recursively expanding finite strings, and refinements of Pascal's triangle. Newman's generalizations of $a(n)$ can be analyzed in the same way, and the results obtained point to possible relations with Conway's theory of games.''

  • 0
    I could not find the paper that you said, however I have found others, and they solve a problem much harder than mine, I just want to prove that the sequence converges. Is this so hard? And another question about the same, I could not prove that the subsequence $ a_{2^k} = 2^{k-1} $ it´s so difficult?2011-09-18
0

Daniel, I bumped into you searching for the sequence of Conway. May I ask if you managed to prove that it converges to 1/2? It seems to be a very interesting sequence and at the moment I am also dealing with batrachion functions. Can we discuss about the sequence you were talking about? :)

  • 0
    Thanks for the comment, I didn't notice that! Do you have any clue for the answer though?2013-12-07