I'm going through Cormen et al.'s Introduction to Algorithms and I am a little thrown off by some of the subtleties of solving recurrences with the substitution method. Given the recurrence:
$$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + 1, $$
We guess that the solution is $T(n) = O(n)$. Thus we try to show that $T(n) \le cn$. By substituting our guess, we are left with,
$T(n) = cn + 1$, which is not $\le cn$.
Makes sense. But then in the next paragraph, he writes that if we guess for $T(n) = O(n^2)$, we can make the solution work. However, wouldn't the solution still be off by a constant of 1, since:
$$T(n) = O(n^2) = 2c(n/2)^2 + 1?$$
Or am I not substituting correctly for $O(n^2)$? Seems like I'm missing something trivial about this.