Proof by Induction: Prove that $2^n > n^2$, for all natural numbers greater than or equal to $5$

Question

Problem: $2^n > n^2, \forall n \in \mathbb{N} , n \geq 5$

Base: $2^5 > 5^2$

Induction Hypothesis: Assume for $n = k \geq 5$ that $2^k>k^2$

Inductive Step: $$2^k > k^2$$ $$2^k \times 2 > k^2 \times 2$$ $$2^{k+1} > 2k^2$$

From there I can finish the proof by asserting that $k^2 > 2k+1, \forall k \in \mathbb{N} , k \geq 3$.

Do I need to prove that $k^2 > 2k+1, \forall k \in \mathbb{N} , k \geq 3$. Or can I substitute it into my inequality?

Answer 1

You need to prove $k^2\color{blue}{\ge}2k+1$ for $k\ge\color{blue}{5}$ (unless your teacher thinks that's obvious enough to skip), although the stronger version you quoted is also correct. The proof does not, however, need induction. because it's equivalent to $(k-1)^2\ge2$.

Answer 2

You can use $$2^{k+1}=2^k+2^k> k^2 +2k+1$$

Answer 3

You do need to prove it, as the onus is on you to demonstrate that you have understood the question.

My favourite method to prove this is to consider $2+\frac1k\le3$ for all $k\ge1$, and multiply through by $k$, then, as $k\ge3$, the RHS becomes $3k\le k^2$.

Answer 4

Still another way:

If $n\ge 5$, we have $$\Bigl(\dfrac{n+1}n\Bigr)^{\!2}=\Bigl(1+\dfrac1n\Bigr)^{\!2}<\Bigl(1+\dfrac15\Bigr)^{\!2}<2,$$ whence, by the inductive hypothesis, $$2^{n+1}=2^n\cdot 2>n^2\cdot 2>n^2\Bigl(\dfrac{n+1}n\Bigr)^{\!2}=(n+1)^2.$$