I am trying to learn how to prove the runtime of a recurrence relation, particularly through induction. I was looking at this lecture PDF, and on the first page, the author writes this:
Recurrence: $T(1)=1$ and $T(n)=2 T(\lfloor n / 2\rfloor)+n$ for $n>1$. We guess that the solution is $T(n)=O(n \log n)$. So we must prove that $T(n) \leq c n \log n$ for some constant $c$. (We will get to $n_0$ later, but for now let's try to prove the statement for all $n \geq 1$.)
As our inductive hypothesis, we assume $T(n) \leq c n \log n$ for all positive numbers less than $n$. Therefore, $T(\lfloor n / 2\rfloor) \leq c\lfloor n / 2\rfloor \log (\lfloor n / 2\rfloor))$, and
$$ \begin{aligned} T(n) & \leq 2(c\lfloor n / 2\rfloor \log (\lfloor n / 2\rfloor))+n \\ & \leq c n \log (n / 2)+n \\ & =c n \log n-c n \log 2+n \\ & =c n \log n-c n+n \\ & \leq c n \log n \quad(\text { for } c \geq 1) \end{aligned} $$
I have two questions:
In the last step, the author omits the $-cn$ and $n$ terms, and I think they did this because setting a bound for $c$ makes these terms irrelevant. Is this correct? If so, I was hoping someone could spell out why these terms can be removed :).
Could something similar be done for proving $\Theta(\cdot)$ (i.e. a lower and upper bound)?