Proof by math induction with inequality example, why is "replacement" allowed?

Question

I have trouble with the understanding of mathematical induction concerning inequalities. For example, the question is: Prove by mathematical induction that $ n ^ 2 <2 ^ n $ if $ \forall n \in {N}$ and $n \geq 5$.

1) The base of induction: for n = 5, we have that $ 5^2 <2^5 $ followed by 25 <32, which is true.

2) The inductive step: assume that it is true for n + 1, then we have the following: $$ (n + 1) ^ 2 <2 ^ {n + 1} $$ $$ n ^ 2 + 2n + 1 <2 ^ n \cdot 2 $$ $$ n ^ 2 + 2n + 1 <n ^ 2 \cdot 2 $$this is a case of "replacing" $ 2 ^ n $ from the second row with the $ n ^ 2 $ from the inductive hypothesis ($ n ^ 2 $ <$ 2 ^ n $). When we simplify, we get the expression $2n + 1 <n^2$, so if we check with some $n$ that is greater than or equal to 5, for example, $ n = 5 $, we get that $ 2 \cdot5 + 1 <5 ^ 2 $, and the next line is $ 11 <25 $, which is true.

I do not understand that "replacement" of $ 2 ^ n $ for $ n ^ 2 $, why is it possible? It is clear that $ n ^ 2 $ is less than $ 2 ^ n $, so we are essentially claiming that something on the right side of the $<$ sign is still higher than the expression on the left side of that $<$ sign, although it is clear that the value of the right side is now lower than it was before this "replacement" , because $n^2 \cdot 2$ is less then $ 2 ^ n \cdot 2 $. How can we still claim something like this, on what basis?

If in the second case, instead of $ 2 ^ n $ from the second row we place $ n ^ 2 $, we get $ 2 ^ n + 2n + 1 <2 ^ n \cdot 2 $, so when we simplify and test with $n=5$, we again get an accurate statement: $ 21.5 <32 $. Here we have inserted a greater value on the left side ($ 2 ^ n $ is greater than $ n ^ 2 $) and we continue to claim that the expression on the left is less than the expression on the right, although it is true, I believe that there are some cases where this "replacement" will not be possible or am I wrong?

Answer 1

It was only ill explained. What is meant is this, in my opinion:

We have to prove $(n+1)^2=n^2+2n+1<2^{n+1}=2^n\cdot 2$. As, by the inductive hypothesis, $n^2<2^n$, it is enough to prove $$n^2+2n+1<2n^2\iff n^2-2n=n(n-2)>1.$$ This is true for $n\ge 5$ since $n(n-2)\ge 5\cdot 3=15$.

Answer 2

This induction proof is not written in the correct order. The inductive step should begin by assuming $n^2<2^n$ for some $n \geq 5$. Then you want to show that $(n+1)^2<2^{n+1}$. You cannot show this by starting with the equation $(n+1)^2<2^{n+1}$. Instead you should start with \begin{align*} (n+1)^2&=n^2+2n+1\\ &<2^n+2n+1 &\text{by the induction hypothesis.} \end{align*} Now in order to show this is $\leq 2^{n+1}$, you need to show $2n+1 \leq 2^n$.

Answer 3

This is basically given by the transitive property of the ordering relation $<$. What's confusing is that the proof you've shown is proceeding backwards - starting at what we want to prove and reducing it to what we know, rather than vice versa. Let me start by supposing that you've already proved that $2n+1<n^2$ for any $n\geq 5$. Then, if we write out the proof of the inductive step in a detailed way, we could say:

Suppose we know that $n^2<2^n$ for some $n$ and wish to show it for $(n+1)$ as well. To do so, let us start with a known statement: $$2n+1<n^2.$$ Now, add $n^2$ to both sides: $$n^2+2n+1<2\cdot n^2.$$ Then, by the inductive hypothesis, we have that $n^2<2^n$. Thus $2\cdot n^2<2\cdot 2^n$. Using the transitive property of $<$, we get $$n^2+2n+1<2\cdot 2^n$$ Simplifying both sides gives $$(n+1)^2<2^{n+1}.$$

Basically, what's happening here is that I've written each statement so that it is implied by the last. So, I can take an inequality $a<b$ and then any $c$ with $b<c$ and weaken the statement to $a<c$, since in that case $a<b$ implies $a<c$. When you work "backwards", as you have done, your legal moves are going from a the current statement to a statement that implies the current one - so, since $a<b$ implies $a<c$ for $b<c$, moving to stronger bounds is okay (as the goal is to arrive at a true statement which then implies all the statements you used before it). That said, even if being able to work backwards is useful, one basically always writes proofs forwards, as it clarifies the logic.