# complexity theory – 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
$$0geq 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 “induction fails” ? because I’ve never heard of such one.