In CLRS, exercise 4.4-5 the following question is asked:
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $$T(n) = T(n-1) + T(n/2) + n$$
In my recursion tree, the sum of level 0 is $$n$$ level 1 is $$(3/2)n - 2/2^1$$ level 2 $$(3/2)^2n-14/2^2$$ level 3 is $$(3/2)^3n - 74/2^3$$ and so on. My issues is that the rule governing the constants 2, 14, 74 etc. is difficult to express as a function of the level so that I can create a sum for all levels of the tree.
Would it be correct to say that the cost at each level of the tree is $$(3/2)^in - O(1)$$ and thus avoid the problem of having to sum all of the constant terms via big O notation, or is this approach incorrect? If so, why and what should I do instead?