How to prove that this sequence converges? ($a_n=a_{a_{n-1}}+a_{n-a_{n-1}}$) 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.
 A: 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.''
A: 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? :)
