Where is the flaw in this proof of $2^n \ge n^2$?

Question

$n^2 \le 2^n\\ \log_2(n^2)\le \log_2(2^n) \qquad \;\quad \mathrm{when} \; n>0\\ 2\log_2(n)\le n\log_2(2)\\ 2\log_2(n)\le n\\ 2\log_2(n)\le n \log_2(n) \quad \mathrm{since} \; \log_2(n) \ge 1 \; \mathrm{when} \; n \ge 2\\ 2\le n \qquad\qquad\qquad\qquad\mathrm{since} \;\log_2(n) > 0$

This proof is inaccurate specifically starting at line 5 since the original inequality is not true for $n=3$. Why did multiplying by a constant greater than 1 make the inequality not true? Or, what rule did I break in this proof?

Answer 1

The problem does not lie with any single step, but rather with the overall structure.

As far as I can tell, you think your proof shows "If $n \ge 2$ then $n^2 \le 2^n$." But that's not what your proof actually shows at all. You seem to be beginning with the property you want to prove ($n^2 \le 2^n$) and manipulating it until you arrive at the condition $n \ge 2$. If this proved anything, it would be "If $n^2 \le 2^n$ then n \ge 2". But if that were what you were trying to prove, you have a different problem, because you are also assuming your conclusion ($n \ge 2$) as a justification for a step in the middle of the "proof", which means you are engaging in a circular argument.

If you want to prove "If $n \ge 2$ then $n^2 \le 2^n$", you need to start with the inequality $n \ge 2$ and manipulate it until you arrive at $n^2 \le 2^n$. In other words, you need to try to rewrite your proof in reverse order. If you do that, I suspect you will find the step that doesn't work.

Answer 2

The issue is that your logic is backwards. You're assuming that $n^2 \leq 2^n$ and concluding that $2 \leq n$, with the side assumption that $n \geq 2$. In other words, this hasn't really proven anything nontrivial.

With many techniques used in basic algebra, this kind of reasoning works because the implications between lines works both ways. For example, $2x = 4$ if and only if $x = 2$. Dividing by 2 can be undone by multiplying by $2$. That's why you can't solve an equation by simply multiplying both sides by $0$; multiplying by $0$ can't be undone, so the resulting equation isn't logically equivalent to the original.

So what's happening here? The step that can't be undone is an instance of transitivity for $\leq$. You have that $2 \log_2(n) \leq n$ and $n \leq n \log_2(n)$, so you conclude that $2 \log_2(n) \leq n \log_2(n)$. But this reasoning doesn't work backwards. If $n \leq n \log_2(n)$ and $2 \log_2(n) \leq n \log_2(n)$, you cannot conclude that $2 \log_2(n) \leq n$. Using transitivity like this is giving up ground.