Prove the following: For n ≥ 4, n ^2 ≤ 2^n I have been asked to prove the following:
For n ≥ 4, n$^2$ ≤ 2$^n$
I will argue by induction the statement P(k): for n ≥ 4, n$^2$ ≤ 2$^n$.
First, consider the base case P(4) = 16 ≤ 16 which is true, so we assume P(n) holds and consider P(n+1).
2$^{n+1}$ = 2$^n$2
We know that 2$^n$2 ≥ 2$^n$ and from our induction hypothesis we also know that n$^2$ ≤ 2$^n$, so we know that 2$^n$2 ≥ 2$^n$ ≥ n$^2$.
This is the part that makes me a bit uncomfortable and I think is wrong:
(n+1)$^2$ ≥ 2$^n$ by our induction hypothesis and definition of inequality.
Then, also by definition of inequality:
2$^n$2 ≥ (n+1)$^2$ ≥ 2$^n$ ≥ n$^2$
Thus, we have completed our induction step and shown that 2$^{n+1}$ ≥ (n+1)$^2$.
I am worried about my jump that (n+1)$^2$ ≥ 2$^n$. Do I need to some kind of subproof here to prove this relation? Any help would be appreciated!

This is more a comment
than an answer,
but it does provide an answer.
In my answer to my own question,
I prove this:
If $n$ and $k$ are integers
and $k \ge 2$
and
$n \ge k^2+1$,
then
$2^n > n^k$.
Here it is:
Prove that $n^k < 2^n$ for all large enough $n$
