Studying for a test in discrete mathematics and I cannot seem to grasp the explanations in the textbook regarding these questions.
Using mathematical induction, prove that
$$2^n > n^2, \text{for } n \ge 5.$$
The answer seems to make some kind of jump in reasoning that I'm currently blind to, just looking for some differing explanations that could hopefully brighten the dark hole I'm stuck in.
On
For $n\geq 5$, let $S(n)$ denote the statement $$ S(n) : n^2 < 2^n. $$
Base step ($n=5$): Since $5^2=25<32=2^5, S(5)$ is true.
Inductive step: Fix some $k\geq 5$ and assume $S(k)$ holds where $$ S(k) : k^2 < 2^k. $$ To prove the inductive step, we must show that $$ S(k+1) : (k+1)^2 < 2^{k+1} $$ follows. Starting with the left-hand side of $S(k+1)$, \begin{align} (k+1)^2 &= k^2+2k+1\tag{expand}\\[0.5em] &< 2^k+2k+1\tag{by $S(k)$}\\[0.5em] &< 2^k+k+1\tag{since $k\geq 5\geq 1$}\\[0.5em] &< 2^k+2^k\tag{by $(\dagger)$, since $k\geq 5\geq 2$}\\[0.5em] &= 2(2^k)\tag{group}\\[0.5em] &= 2^{k+1}, \end{align} we reach the right-hand side of $S(k+1)$, completing the inductive step.
Thus, by mathematical induction, for all $n\geq 5$, the inequality $S(n)$ is true.
Note: By $(\dagger)$ I meant that if $n\geq 2$, then $n+1<2^n$, another inequality fairly easy to prove by induction.
Base case: $n=5$: You have that $2^5 = 32 > 25 = 5^2$
Suppose for our induction hypothesis that $2^n> n^2$ for some $n\geq 5$.
Then: $2^{(n+1)} = 2\cdot 2^n>^{I.H.} 2\cdot (n^2) = n^2 + n^2 $
$= n^2 + n\cdot n >^{(\dagger)} n^2 + 3\cdot n = n^2 + 2n + n>^{(\dagger)} n^2 + 2n + 1 = (n+1)^2$
The steps I made at each $(\dagger)$ are each due to the fact that we know that $n\geq 5>3>1$.
Thus if it is true for $n$, it follows it is true for $n+1$ and the result is proven for all $n\geq 5$.
In general, if a statement is not always true, you should use all pieces of information you know (in this case that $n\geq 5$).