Cannot see why this formula is wrong In the book of "Introduction to Algorithm 3rd Edition", p.86, there is subtitled, "Avoiding pitfalls", and it states
When

$T(n) = 2 \cdot T(\lfloor(n/2)\rfloor)+n$

, and if we want to prove $T(n)=O(n)$ by guessing $T(n) \leq cn $ and the argument of this

$T(n) \leq 2(c\lfloor(n/2)\rfloor) +n$
$\leq cn + n$
$=O(n)$     <== Wrong!

since $c$ is a constant.
I don't understand why above is wrong? Could someone explain above, please?
 A: Firstly let me note, that for $n=2^k$ and $T(n) = 2 \cdot T(\lfloor(n/2)\rfloor)+n$ we can obtain $T(n)=nT(1)+n \log_2 n$, so it is not $O(n)$.
About mistake in proof: 86p. clearly says reason as authors see it

*

*"The error is that we have not proved the exact form of the inductive hypothesis, that is, that $T(n) \leqslant cn$. We therefore will explicitly prove that $T(n) \leqslant cn$  when we want to show that $T(n) =O(n)$."

But, as we know, mathematical induction
$$\forall P\Big(P(0) \land \forall k(P(k) \Rightarrow P(k+1)) \Rightarrow \forall n(P(n))\Big)$$
does not require explicit prove of inductive hypothesis $P(k)$, but the implication $\forall k(P(k) \Rightarrow P(k+1))$.
So to prove exact form of induction firstly we need clearly set what is $P$.

*

*If we assume, that $P(n)$ is "$T(n) =O(n)$", then we come to question how to understand initial step of induction, which, in this case, becomes $T(1) =O(1)$. As we know in formal definition of "$T(n) =O(n)$", the "$n$" is the variable in definition under universal quantifier, it is so called bound variable. Exact formulation of sentence $f(x) \in O(g(x))$, $x \to x_0$ means, that we need two functions $f,g$ from variable $x$ and limit point $x_0$. So we can consider, that $P(n)$ is "$T \in O(n)$" and under "$n$" we understand identity function $I(n)=n$. So formally we come to "$T \in O(I)$".


*If we assume, that  $P(n)$ is "$T(n) \leqslant cn$", this will fix $c$. So initial step of induction, in this case, is $T(1)\leqslant c $. Now we need to prove $P(k) \Rightarrow P(k+1)$, which is $T(k) \leqslant ck \Rightarrow T(k+1) \leqslant c(k+1)$. But using suggested in book proof we obtain only $T(k+1) \leqslant c(k+1)+(k+1)$, which, sure, is not what we wanted.
