Proof by Smallest counterexample: for integers >= 5, $2^n$ > $n^2$

Question

Can anyone explain how they went from

$2^x$ to $x^2$ from lines 12 to 13? This has to be a mistake in the textbook proof, right?

Answer 1

The words here are absolutely critical, and the logic of the proof is a little hard to follow. I will use the symbol $\Rightarrow$ to represent "implies" and $\Leftrightarrow$ to represent "if and only if"/"is equivalent to". Here is an explanation of the argument starting from $(12)$.

1. Tha assumption (in context) is that $\boxed{x\ge6}$.
2. The goal (in context) is to show that $2^x>x^2$ so that $x$ wasn't actually a counterexample.
3. They have shown (in context) equation $\boxed{(12)}$.
4. "We will be finished once we can prove [$(13)]$." is not a claim of $(13)$, it's a claim that $(13)$ and $(12)$ together would give the desired result: $\boxed{\left((12)\text{ and }(13)\right)\Rightarrow\text{goal}}$. This implication is true because of how inequalities work. $a>b\ge c\Rightarrow a>c$ in general, so $2^x>2x^2-4x+2\ge x^2\Rightarrow 2^x>x^2$.
5. "To prove Equation (18), we just need to prove [$(14)$]". I think "$(18)$" is a typo for "$(13)$" here. So this is saying $\boxed{(14)\Rightarrow(13)}$. Why? Well "We got $(14)$ from $(13)$ by adding $2-x^2$ to both sides", so that if we subtracted $2-x^2$ from both sides of $(14)$, we would get $(13)$.
6. "Notice that Equation $(14)$ can be rewritten [as $(15)$]." means that $\boxed{(14)\Leftrightarrow(15)}$.
7. "So we have reduced the problem to proving Equation $(15)$" means that $\boxed{(15)\Rightarrow\text{goal}}$ (in context). Why? Well $(15)\Rightarrow(14)\Rightarrow(13)$ (by my points 6. and 5.), and we have $(12)$ (my point 3.), and $\left((12)\text{ and }(13)\right)\Rightarrow\text{goal}$ (my point 4.).
8. "and to prove that, it certainly is enough to prove [$(16)$]." means $\boxed{(16)\Rightarrow(15)}$. Why? Squaring a number that's at least $1$ makes it bigger (or the same) and if we have $x-2\ge2$ then $x-2$ is a number that's at least $1$, so $(x-2)^2\ge(x-2)\ge2$ so $(x-2)^2\ge2$.
9. "and that's true because $x\ge6$ (all we need is $x\ge4$)." means $\boxed{x\ge6\Rightarrow x\ge4\Rightarrow (16)}$. Why? The first implication is because $6\ge4$ and the second is by subtracting $2$ from each side of $x\ge4$.
10. They didn't write this explicitly, but since we are assuming $x\ge6$ (my point 1.), we get $(16)$ (by my point 9.), so we get $(15)$ (by my point 8.), so we get the goal (by my point 7.).