I'm trying to show that merge sort is $O(n^2)$ using induction. (I'm just concerned with powers of two for simplicity). However, I'm stuck at the last inequality
Basis step:
Show that there exists a constant $C$ for all $n=2$ such that: $$\begin{align*}M(2) &\leq C \cdot (2)^2\\ 1 &\leq 4C \\\end{align*}\\ \therefore \text{holds for $n=2$ with $C \geq \frac{1}{4}$} $$
Inductive Hypothesis:
There exists a constant $C$ for all $n>1$ such that: $$M(n) \leq C \cdot n^2$$
Inductive step:
There exists a constant $C$ for all $n>1$ such that: $$\require{cancel}\begin{align*} M(2n) &\leq C \cdot (2n)^2 \\ \text{Show that: }\\ M(2n) &\leq C \cdot 4n^2 \\ 2 \cdot M(n)+2n &\leq C \cdot 4n^2 \tag{Recurence relation} \\ 2 \cdot M(n) &\leq C \cdot 4n^2 - 2n \\ \cancel{2}(M(n)) &\leq \cancel{2}(C \cdot 2n^2 - n) \\ M(n) &\leq C \cdot 2n^2 - n \\\end{align*}$$
From here if I can show that $ C\cdot n^2 \leq C \cdot 2n^2 - n$ then using the Inductive hypothesis ($M(n) \leq C \cdot n^2$) I can show that the proof holds.
How do I show $ C\cdot n^2 \leq C \cdot 2n^2 - n$? And how do I find the min value of $C$ where this holds?
There are two things you need to find: any positive $n_0$ and any positive $C$ such that your above relation holds for $n>n_0$.
It doesn't have to hold for all $n$: it only has to hold for "sufficiently large" $n$. And you don't need to find the minimum $C$. The "minimum" $C$ will depend on which $n_0$ you chose anyway.
The easy way to do it is just pick an arbitrary value of $C$, such as $C=1$ and ask when is $n^2 \le 2n^2 - n$ ? Answer, for $n \ge 1$. So one solution is $C=1$, $n_0 = 1$.
If you want to find all possible witnesses to $C$ and $n_0$, then solve:
$$C\cdot n^2 \le C\cdot 2n^2−n$$ $$n \le Cn^2$$ $$1 \le Cn$$
So any value of $C$ and $n_0 \ge \frac{1}{C}$ will satisfy the relation.
Note that $O(n^2)$ isn't a tight upper bound on mergesort, you could prove that it is $O(n~\log(n))$ as well.