1
$\begingroup$

This question already has an answer here:

I've been asked to prove by induction that $n^2\leq 2^n$, and told it is true $ \forall n\in \mathbb{N},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^2\leq 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^2\leq 2^k$

$=2k^2\leq2^{k+1}$

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

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

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

$=2k+1\leq k^2$

(By assumption)

$=2k+1\leq 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+1\leq 2^k$? Thank you in advance.

$\endgroup$

marked as duplicate by dantopa, Cesareo, Lee David Chung Lin, Eevee Trainer, Leucippus Mar 27 at 4:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Such a neat reasoning, I feel silly I couldn't do this myself, haha. Excelent, @fleablood, I appreciate the fact that you took the trouble to answer my question. Thank you! $\endgroup$ – Lafinur Mar 26 at 19:30
  • $\begingroup$ The last line in the first part should probably read $2*2^k \color{red}= 2^{k+1}.$ $\endgroup$ – CiaPan Mar 26 at 20:36
  • $\begingroup$ ooppps......... $\endgroup$ – fleablood Mar 26 at 21:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.