Solving recurrence $T(n) = 8T(\frac n3) +T(\frac n3 + 1) + n$
Is there some general idea when solving recurrences like this? I tried substituting $n\to 3n$ and got:
$T(3n) = 8T(n) + T(n + 1)$ which is a little more approachable but still, I can't use the characteristic polynomial on this, how would I solve it?