Proof by Induction for $n^2\leq2^n$ .

Question

I was given the following as part of a course on Abstract Mathematics that I am currently busy with. It is from a Book "An Introduction to Mathematical Reasoning" by Eccles.

For all integers $n$ such that $n\geq4$, we have the inequality $n^2\leq2^n$ . Construct a proof. The inductive step of a proof by induction on $n$ reads

$$k^2 \leq2^k \implies (k+1)^2 \leq 2^{k+1}$$ For integers $k\geq 4$.

The book then claims, "We can achieve the right-hand side of the conclusion inequality by multiplying the hypothesis inequality by $2$, giving:"

$$2k^2 \leq 2^{k+1}$$

I do not understand how $2k^2 \leq 2^{k+1}$ was arrived at.

Could somebody expand the previous line?

Answer 1

Induction hypothesis: Let $k\geq 4$ be such that $k^2\leq 2^k$. Then, we can multiply both sides of this equation by $2$ to get $2\cdot k^2\leq 2\cdot 2^k$ or $2k^2\leq 2^{k+1}$. It remains now to show by you that you have $(k+1)^2\leq 2k^2$ for $k\geq 4$. I hope this clarifies your problem!

Answer 2

We assume that:

$$k^2 \leq 2^k \tag 1$$ holds true.

We wish to show that, if we make this assumption, the following: $$(k+1)^2 \leq 2^{k+1} \tag 2 $$ also holds true. Noting that $2^{k+1}=2\cdot 2^k$, we can multiply $(1)$ by 2 to give:

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

It then suffices that from:

$$p\leq q\leq r \implies p\leq r$$ that you just need to prove:

$$(k+1)^2\leq 2k^2$$ when $k\geq 4$. Can you do this?