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
    @August, could you point to one of the many sources you claim say it's trivial?2011-09-29