How to prove that this sequence converges? ($a_n=a_{a_{n-1}}+a_{n-a_{n-1}}$)

Solution 1:

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