Proving guess wrong used for substitution method

Question

Following is my recurrence relation :

$T(n) = 2T(n−1) + c_1$. Complexity: $O(2^N)$.

I want to prove it by substitution method/ mathematical induction (You can get insight of it from : http://www.cs.cornell.edu/courses/cs3110/2014sp/recitations/24/using-the-substitution-and-master-method.html)

Now even if I am making guess: $T(n) = kn-b$ then also I am able to prove $T(n) = O(n)$, which is obviously wrong.

Can anyone prove, why it is wrong ?

P.S. I know we can solve it by other methods. I want to know how we get to know , our guess is wrong.

Answer 1

Assume $T(n)=kn-b$

Then $T(n+1)=kn+k-b$

Inserting the reccurence relation gives $$kn+k-b=2kn-2b+c_1$$ for all $n$.

Both sides are linear functions depending on $n$. If both sides would be equal FOR ALL n, the linear coefficients would have to be the same. But $k\ne 2k$

What about $k=0$ ? In this case, we get $c_1=b$. Therefore, only constant sequences are possible with the given guess.

So, the guess must be wrong, except for constant sequences.

Answer 2

Let $T(0)=T_0$ and iterate \begin{align} T(1)&=2T_0+c_1,\\ T(2)&=2T(1)+c_1=2(2T_0+c_1)+c_1=2^2T_0+(2+1)c_1,\\ T(3)&=2T(2)+c_1=2(2^2T_0+(2+1)c_1)+c_1=2^3T_0+(2^2+2+1)c_1,\\ \vdots\\ T(n)&=2^nT_0+\sum_{k=0}^{n-1}2^k\cdot c_1=2^nT_0+(2^n-1)c_1=2^n(T_0+c_1)-c_1. \end{align} One particular constant solution is for $T_0=-c_1$. All others have growth as $O(2^n)$.