inducción sobre secuencias

Question

Se que esta secuencia se encuentra en algunos papers etc, pero en ninguna parte se resuelve este problemita, solo lo discuten como un trivial, al menos yo no pude hacerlo, por eso pido ayuda. Sea la siguiente secuencia definida recursivamente: $$ \eqalign{ & a_1 = a_2 = 1 \cr & a_n = a_{a_{n - 1} } + a_{n - a_{n - 1} } \cr} $$ demostrar que la subsecuencia $ a_{2^k} $ es tal que $$ a_{2^k } = 2^{k - 1} $$

EDITADO: Sólo he cambiado los valores iniciales sustituyendo $a_0 $ por $a_2$ porque no se sostiene en el otro caso, ahora sí

Answer 1

En realidad no es cierto. Si introducimos $k=0$ la reclamación es $a_1=2^{-1}$ lo que contradice la definición $a_1=1$ .

Pero si se cambia el reclamo por $a_{2^k}=2^k$ , entonces se puede demostrar por inducción larga en $n$ que $a_n=n$ para todo $n\ge 1$ .