Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I think the sequence is Hofstadter-Conway $10000 Sequence!… – 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

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

share|cite|improve this answer
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? :)

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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