Find all natural $n$ for which $2^{n} \leq n^{2}$.

#
The exponential function grows faster than the quadratic. Using induction on $n$, show that for $n>4$, $2^{n}>n^{2}$.

## Solution

Direct verification shows that the values $n=2,3,4$ work, but $n=1$ does not.

We will prove by induction on $n$ that $2^{n}>n^{2}$ for $n>4$. The base case ($n=5$) is obvious.

Induction step. $2^{n+1}=2 \cdot 2^{n}>2 n^{2}>(n+1)^{2}$. Indeed, $2 n^{2}-(n+1)^{2}=\left(n^{2}-2 n+1\right)-2=(n-1)^{2}-2>0$ for $n>4$.

## Answer

$2,3,4$.