Proving inequalities using induction and assumptions

Question

Having trouble deciding how to prove certain inequalities using induction.

For instance prove $n^2 \leq 2^n$ for all $n \in \mathbb{N}$ and $n \geq 4$

Attempt:

I know the trick is to show $n^2<?<2^n$

When doing this is it under the assumption that $n \geq 4$?

Proof:Assume $k^2 \leq 2^k$

then for $k \geq 4$

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

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

My biggest question is, when proving these inequality relationships should I keep the assumption that $k \geq 4$ since $k^2 \leq 2^k$ is not true for $k=3$?

Answer 1

When you're doing a proof by induction, you always need to include the base case. In this case, you need to clearly say that $4^2\leq 2^4$.

A common metaphor for proofs by mathematical induction is an infinite number of dominoes stacked in a line. The base step is like one of the dominoes being knocked over, and the induction step is showing that each domino would knock over the "next" one if it were to be knocked over. Both steps are critical to showing that all of the dominoes "after" the first one will be knocked over.

Answer 2

Yes, you should keep that assumption. Often, it turns out that that intermediate inequality holds undear weaker assumptions, but you cannot know from the start whether or not that is a the when dealing with a specific inequality.