Find recurrence $T(n) = T(\frac {n - 1}2) + T(\frac {n - 2}2) +n$
Usually for recurrences in the form of $T_n = T_{n-1} + T_{n-2}$, I use the characteristic polynomial, but I'm not sure if it works in this case.. and can't really use it.
Should I take 2 separate cases? for n even and n odd?