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

-

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