How can I find the complexity of this recurrence?

24 Views Asked by At

I've to solve the following recurrence:

$T(n) = 2T(n-1) - 1$, for $n \geq 1$

$T(n) = 1$, for $n = 0$

I'd easily proved that $T(n) = O(2^n)$, however it seems that $T(n)$ is $O(1)$ actually.

So, how can I prove it? Any ideas?