How to properly solve T(n) = T(n-1) + O(2^n)? I've been trying to solve this recurrence: T(n) = T(n-1) + O(2^n)

My approach when writing everything out and solving the geometric series was: T(n) = O(2^n).

T(n) = c2^n * (1 + 1/2 + 1/4 + ...)

= c2^n * (1/2)^i for i from 0 to infinity

T(n) &lt;= d*2^n for some constant d.
What you did is fine for most purposes. If you want a really rigorous proof without "dot dot dots," then you need to use induction. For that you need to make the constant in big-Oh explicit, and use your "back of the envelope calculation" to come up with the induction hypothesis.