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 know that this sequence is found in some papers etc, but nowhere is this little problem solved, only discuss it as a trivial, at least I could not do it, so I ask for help. Let the following sequence defined recursively: $$ \eqalign{ & a_1 = a_2 = 1 \cr & a_n = a_{a_{n - 1} } + a_{n - a_{n - 1} } \cr} $$ prove that the subsequence $ a_{2^k} $ is such that $$ a_{2^k } = 2^{k - 1} $$

EDITED: I only changed the initial values replacing $a_0 $ by $a_2$ because it does not hold in the other case, now yes

share|cite|improve this question

It's not actually true. If we plug in $k=0$ the claim is $a_1=2^{-1}$, which contradicts the definition $a_1=1$.

But if you change the claim to $a_{2^k}=2^k$, then you can prove by long induction on $n$ that $a_n=n$ for all $n\ge 1$.

share|cite|improve this answer
You're wrong in saying that $ a_n = n $ that is not true I let the first term of the sequence 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9 – August Sep 28 '11 at 2:57
I'm right according to your original definition. Don't change the question and then criticize answers from not magically changing to follow your revisions! (And, at the time of this writing, the question still does not make $a_1=1/2$). – Henning Makholm Sep 28 '11 at 3:03
Ok, then let's say that for all k> 2 is true – August Sep 28 '11 at 3:12
At least in various papers says that this fact it´s trivial, but i can´t prove it – August Sep 28 '11 at 3:18
See – Robert Israel Sep 28 '11 at 4:13

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.