Failing to solve a recurrence by induction
Ok lets try solving this by substitution ,
$T(n) = 2T(n-1) + 1$
from this we know , $T(n-1) = 2T(n-2) + 1$
so $T(n) = 2(2T(n-2) + 1) + 1$
$T(n) = 2^2T(n-2) + 3$
lets substitute one more time
$T(n-2) = 2^2T(n-3) + 1$
$T(n) = 2^2(2T(n-3)+1) + 3$
$T(n) = 2^3 T(n-3) + 7$
Hopefully you can notice the pattern now $T(n) = 2^{k}T(n-k) + 2^{k}-1$
So , for $k = n$
$T(n) = 2^{n}T(n-n) + 2^{n}-1$ , we know that $T(n-n) = T(0) = 1$
$T(n) = 2^{n} + 2^{n}-1$
so clearly , $T(n) = O(2^n)$