Solving recurrences by substitution 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.
Assuming for simplicity that $n$ is even, if we guess that $T(n) \leq C^2n$ then we can prove our guess by induction (for powers of 2) for an appropriate value of $C$ since
$$
T(n) = 2T(n/2) + 1 \leq C(n/2)^2 + 1 = \frac{C}{4} n^2 + 1
$$
is smaller than $Cn^2$ as long as $C \geq 4/3$ (assuming $n \ge 1$).