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

-
I think the sequence is Hofstadter-Conway $10000 Sequence! mathworld.wolfram.com/… – Jineon Baek Aug 17 '11 at 11:00 but i can´t prove that it converges <.<, i don´t care the value, only that converges )= – Daniel Aug 17 '11 at 11:10 "$a_0=a_1=a_n$"? – Hans Lundmark Aug 17 '11 at 13:26 @Daniel: I edited the initial conditions, please check to see if that is what you intended. The original statement doesn't make sense. – Willie Wong Aug 17 '11 at 13:35 @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$. – Willie Wong Aug 17 '11 at 13:40 ## 2 Answers 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.

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

-
I can not find the document D: – Daniel Aug 23 '11 at 19:39
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? – Daniel Sep 18 '11 at 19:11

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? :)

-
This is a comment not answer. – user52045 Dec 7 '13 at 12:16
Thanks for the comment, I didn't notice that! Do you have any clue for the answer though? – Agnes Dec 7 '13 at 13:48