Failing to solve a recurrence by induction My question is strongly related to the one asked here:
How do I show T(n) = 2T(n-1) + k is O(2^n)?
$$T(n)=2T(n-1)+1$$
Going with the steps, I reached the point where:
$$c*2^{n}\geq c*2^{n}+1$$
which implies
$$0\geq 1$$
which is false for all possible values of $c$ and thus the claim $T(n)=O(2^{n})$ should be incorrect.
However, most answers to the question just mention that in such case, one should try alternative methods to find/prove the upper bound. I don't understand how should I be able to justify that, is this a scenario in which &quot;induction fails&quot; ? because I've never heard of such one.
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)$