Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$
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 &gt; 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.