Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$.The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing  $\qquad \begin{align*} T(n) & \leq 2(c \lfloor n/2 \rfloor ) + n \\ &\leq cn +n \\ &=O(n) \quad \quad \quad \longleftarrow \text{ wrong!!} \end{align*}$  since $c$ is constant.The error is that we have not proved the exact form of the inductive hypothesis.Above I have exactly quoted what the book says. Now my question is why cannot we write $cn+n=dn$ where $d=c+1$ and now we have $T(n) \leq dn$ and hence $T(n) = O(n)$?Note: The correct answer is $T(n) =O(n \log n).$  The book I am referring here is Introduction to algorithms by Cormen et al., page 86, 3rd edition.
Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$
proof techniques;asymptotics;recurrence relation;landau notation;induction
The authors give the answer:The error is that we have not proved the exact form of the inductive hypothesis, that is, that $T(n) \leq cn$.Granted, that is hard to understand if you are not used to do inductions (right), because they do not do the induction explicitly/rigorously. In short: you need to have one constant $c$ for all $n$, but this (un)proof constructs many (one per $n$).In long, remember what $T(n) \in O(n)$ means:$\qquad \displaystyle \exists c \in \mathbb{N}.\, \exists n_0 \in \mathbb{N}.\, \forall n \geq n_0.\, T(n) \leq cn$or, equivalently,$\qquad \displaystyle \exists c \in \mathbb{N}.\, \forall n \in \mathbb{N} T(n) \leq cn$.The second form works better for an induction as you know the anchor. So you need one constant $c$ that provides an upper bound for all $n$.Let's inspect what the induction does:Induction anchor: The anchor of $T$ is not explicitly given, but it's constant, so we find a suitable $c$.Induction hypothesis: There is some $c$ so that $T(k) \leq cn$ for all $k\leq n$, for some arbitrary but fixed  $n$.Inductive step: as shown in the question, construct $d > c$ so that $T(n+1) \leq dn$.So, in effect, we construct a new constant for every $n$. That does not fit the definition of $O$ at all! And, worse, it is completely meaningless: every function can be bounded by any other function if you can adjust the factor with $n$.Regarding the induction proof, $c$ has to be part of the claim (and it is, hidden in the $O$), that is bound outside of the induction. Then, the same $c$ shows up in anchor, hypothesis and step. See the last part of this answer for an example.