How to solve recursion with two separate converges rates

Question

What is the correct way to solve the following recursion: $T(n)=T(\lceil\frac{n}{2}\rceil) + T(n-2)$

Or basically any recursion that has two parts which converge in a different rate.

I'm trying to get big $O$ approximation, as tight as possible, but I couldn't figure it out with any "traditional" approach.

Answer 1

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