[Math] Solving recurrence relation: $T(n)=2T(n-1)+1$, using recursion tree and substitution

Question

Given this recurrence relation: T(n)=2T(n-1)+1, I am trying to find the tightest bounds possible. I have already figured the recurrence tree to look like this:

Which would mean n levels, and 2^n work per level, meaning it should be O(2^n), correct? Assuming that's right, how do I begin to prove it with the substitution method?

Answer 1

Hint. You may obtain an explicit formula for $T_n$, by observing that

$$ (T_n+1)=2(T_{n-1}+1),\quad n=1,2,3,\cdots. $$

Then deducing an asymptotic expansion is straightforward.