How to solve recursion with two separate converges rates

If you take the initial conditions $T(0) = 0$ and $T(1) = 1$ then you get A018819 (up to shift), which is essentially A000123. The asymptotics are known to be $T(n) = n^{Theta(log n)}$. The references under the second entry contain more accurate asymptotic information.

More explicitly, A018819 satisfies the recurrence $a(2m+1) = a(2m) = a(2m-1) + a(m)$, with $a(0) = a(1) = 1$. You can show inductively that $a(n) = T(n+1)$. Indeed:

• If $n = 2m+1$ then $$T(n+1) = T(2m+2) = T(m+1) + T(2m) = a(m) + a(2m-1) = a(2m) = a(2m+1) = a(n).$$
• If $n = 2m$ then $$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).$$