Fdtxjr

I've been asked to prove by induction that $n^2leq 2^n$, and told it is true $ forall nin mathbbN,n>3$

I think I have found the right way to the proof, but I'm not sure since I get stuck half-way there. What I did was taking a base case of $n=4$ and tested it, and it resulted to be true. Then I assumed it would be true for some number $k$, such that $n=k$ and $k^2leq 2^k$, and attempted to prove

$(k+1)^2 leq 2^k+1$

And this is how I attempted to prove this. First of all, I started with my assumption.

$=k^2leq 2^k$

$=2k^2leq2^k+1$

Then I tried to prove that $(k+1)^2 leq 2k^2$, for this would imply my thesis, i.e. $(k+1)^2leq2^k+1$. So I went forth on my effort:

$(k+1)^2≤2k^2$

$=k^2+2k+1leq2k^2$

$=2k+1leq k^2$

(By assumption)

$=2k+1leq 2^k$

Now that I simplified it, I need to prove this is true; this is, prove that $(k+1)^2 leq 2k^2$. So I take a base case of $n=4$ and in deed it satisfies the inequality. So I assume it is true for some number $j, k=j$ and try to prove it. Nevertheless I have failed in trying to prove this, I don't really know if my steps so far are right or wrong. Is my reasoning okay? And if its, how can I prove $2k+1leq 2^k$? Thank you in advance.

You need to prove $2k + 1 le k^2$.

Do it this way: $1 < k$ so $2k + 1 < 2k + k = 3k$. And $3 < k$ so $3k < k^2$.

So to put it together:

Induction step:

If $k^2 < 2^k; k > 3$ then

$(k+1)^2 = k^2 + 2k + 1 < $

$k^2 + 2k + k = k^2 + 3k < $

$k^2 + k*k = 2k^2 < $

$2*2^k = 2^k+1$.

.....

.... or simply note...

$2k + 1 < k^2 iff$

$1 < k^2 - 2k iff$

$2 < k^2 - 2k + 1 = (k-1)^2$.

And $k-1 ge 3$ the $(k-1)^2 ge 9 > 2$.