Currently studying "Introduction to Algorithms" , currently stuck at trying to verify an upper bound to a recurrence via substitution when I already know for sure from another method that it is correct.
For $T(n) = T(n/2) + n$, I know from summating the cost at each level on the recurrence tree that it forms a geometric progression, so in the end, the upper bound is $\cal O(n)$.
However, when I substitute $T(n) = cn$, $c$ is some constant into the recurrence, I end up getting $T(n) \leqslant cn + n - c$ which doesn't conclusively show that $\cal O(n)$ is the upper bound for $T(n)$, even though i know for a fact, by the proof above and from googling that it is $\cal O(n)$.
Hence my question is why doesn't the verification using substitution work? Am I doing something wrong? Or is there some way to proceed from my dead end that leads me to conclude $T(n) = \cal O(n)$?
Let $n=2^k$, $k=0,1,2,\ldots$ and assume $T(1)=1$. Then \begin{align} T(2^0)&=1\\ T(2^1)&= T(2^0) + 2^1 = 1 + 2 = 3\\ T(2^2)&= T(2^1) + 2^2 = 3 + 2^2 = 7\\ T(2^3)&= T(2^2) + 2^3 = 7 + 8 = 15\\ &\ \ \vdots\\ T(2^k) &= 2^{k+1}-1, \end{align} hence $T(n) = 2n-1$, so that $T(n)\in\Theta(n)$.