I see this in CLRS:
We can use the substitution method to establish either upper or lower bounds on a recurrence. As an example, let us determine an upper bound on the recurrence $T(n)=2T(\lfloor n/2\rfloor)+ n$. We guess that the solution is $O(n\lg n).$ The substitution method requires us to prove that $T(n)<=cn \lg n$ for an appropriate choice of the constant c>0.
And next :
With T(1)=1, we derive from the recurrence that T(2)=4 and T(3)=5. Now we can complete the inductive proof that $T(n) <= cn \lg n$ for some constant $c>1$ by choosing $c$ large enough so that $T(2)<=c_2 \lg 2$ and $T(3)<= c_3 \lg 3$. As it turns out, any choice of $c >= 2$ suffices for the base cases of $n >= 2$ and $n >= 3$ to hold.
So question is why we can change $c$? Should constant be fixed for using mathematical induction? (There is also quantifier $\exists \ c: f(n)<=cg(n)\ \forall n >= n_0$ in definition of $O$) Thanks.