1
$\begingroup$

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

1 Answers 1

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

  • 0
    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, 92011-09-28
  • 0
    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$).2011-09-28
  • 0
    Ok, then let's say that for all k> 2 is true2011-09-28
  • 0
    At least in various papers says that this fact it´s trivial, but i can´t prove it2011-09-28
  • 0
    See http://oeis.org/A0040012011-09-28
  • 0
    I've never understood how in all the papers say it mention it as a trivial so I will not show, yet when I have asked no one ever responds, perhaps very long induction? and thanks for the site, but I can not find it, I saw that show the result but do not prove2011-09-28
  • 0
    In fact all the papers don´t attack the problem of this subsequence, only they use it, noone knows how to prove this fact? Or has a link that they prove it? It is so difficult, maybe I´m the stupid ...2011-09-28
  • 0
    @Robert Israel In the link the link you gave me, there is no proof about that, it looks like I'm asking something too much trivial , because noone wants to answer me and give me links to pages that also say that this fact is trivial, sorry for be so stupid but I could not did it. )=2011-09-29
  • 0
    It only appear a relation but it´s also difficult to prove, with this I can prove the problem ... $$ a_{2^n - i} = a_{2^n } \,\,\,\,i = 1..n - 1 $$2011-09-29
  • 0
    @August, could you point to one of the many sources you claim say it's trivial?2011-09-29