Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|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 oeis.org/A004001 –  Robert Israel Sep 28 '11 at 4:13

Your Answer

 
discard

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.