Cómo resolver la recursión con dos tasas de converges separadas

Question

¿Cuál es la forma correcta de resolver la siguiente recursión? $ t (n)= t (\ lceil \ frac {n} {2} \ rceil) + t (n-2) $

o básicamente cualquier recursión que tiene dos partes que convergen en una tasa diferente.

Estoy tratando de obtener gran $ o $ aproximación, lo más ajustado posible, pero no pude resolverlo con ningún enfoque "tradicional".

Answer 1

Si toma las condiciones iniciales $ t (0)= 0 $ y $ t (1)= 1 $ Luego obtendrá a018819 (hasta turno), que es esencialmente a000123 . Se sabe que los asintóticos son $ t (n)= n ^ {\ theTa (\ log n)} $ . Las referencias bajo la segunda entrada contienen información asintótica más precisa.

Más explícitamente, A018819 satisface la recurrencia $ A (2M + 1)= A (2M)= A (2M-1) + A (M) $ , con $ a (0)= a (1)= 1 $ . Puede mostrar inductivamente que $ a (n)= t (n + 1) $ . De hecho:

• si $ n= 2m + 1 $ luego $$ t (n + 1)= t (2m + 2 )= T (M + 1) + T (2M)= A (M) + A (2M-1)= A (2M)= A (2M + 1)= A (N). $$ < / li>
• si $ n= 2m $ luego $$ t (n + 1)= t (2m + 1)= T (M + 1) + T (2M-1)= A (M) + A (2M-2)= A (M) + A (2M-1)= A (2M)= A (N). $$