The recurrence $T(n) = 2T(n-1) + 1$ has the solution $T(n) = O(2^n)$. show that a substitution proof fails with the assumption $T(n) <= c2^n$, where $c>0$. Then show how to subtract a lower-order term to make a substitution proof work.
This is question 4.3-3 of Introduction to Algorithms.
Using substitution, I'm getting - $T(n) \le c2^n + 1$ Because of $+1$, this is failing.
Now, if I use a constant d as a lower-order term, I get $T(n) \le c2^n -d$
Substituting this, we get $T(n) \le c2^n -2d + 1$
I cannot prove this time complexity with substitution by taking any lower-order term.
You were on the right track. Here we finish off your proof of the bound. We assume that $ T(n) \leq c2^n - d $ for some constants $c,d$ and substitute:
$$ T(n) \leq 2 \left( c2^{n - 1} - d \right) + 1 $$ $$ \leq c2^n - 2d + 1 $$ $$ \leq c2^n - d $$
which holds when $d \geq 1$. And so we conclude $T(n) \leq c2^n - d = O(2^n)$. Note that if $T(1) = 1$ then it can be shown that $T(n) = 2^n - 1$.