I'm a self-taught and I'm studying from CLRS. I'm having difficulty with this recurrence relation: $$T(n)=3T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + n$$
The problem is that I can "prove" that $T(n) = \mathcal{O}(n)$. It's absurd. My inductive hypothesis about $\mathcal{O}(n)$ is: $$\exists c \gt 0 \,\,\exists n_0 \gt 0 \,\,\exists b \ge 0 \quad\forall n_0\le k\lt n \quad T(k) \le ck - bn \le ck $$
From here I haven't problem during the "proof": $$\begin{align} T(n) &\le 3\left(c\left\lfloor{\frac{n}{2}}\right\rfloor - bn\right) + n \\ &\le 3\left(c\frac{n}{2} - bn\right) + n \\ &= \frac{3}{2}cn - 3bn + n \\ &= \frac{3}{2}cn -n(3b - 1) \qquad\qquad (1st) \\ &\le cn \end{align}$$
The latter holds $\forall b \ge \frac{c+2}{6}$ and it comes from: $$\frac{3}{2}cn - n(3b - 1) \le cn$$
--EDIT--
It's also easy to prove that
$$(1st) \le cn - bn$$
It holds $\forall b \ge \frac{c+2}{4}$
So $$T(n) \le cn - bn$$
--END EDIT--
So I think that the hypotheses are wrong. Probably I misunderstanding subtraction of lower-order term. What are the constraints to apply this technique? Only that $T(k) \gt 0$? In this recurrence the latter seems valid.