Which natural numbers satisfy $2^n > n^2$?

Question

Which natural numbers satisfy $2^n > n^2$ ?

My work. Step 1: $n = 1 $, $2^1 > 1^2$. True.

For $n = k$, $2^k > k^2$. For $n = k+1$, $$ 2^{(k+1)} > (k+1)^2 \\ 2\cdot 2^k>k^2+2k+1 \\ 2^k+2^k > k^2+2k+1$$

• $2^k > k^2 \text{ - from step 1}$

• $2^k > k^2+2k+1$

How I can find the numbers now?

Answer 1

HINT: Check if your mathematical statement is valid for $n=2,3$ and then apply strong form of mathematical induction to disprove the given statement.

Answer 2

The solution of this would be $n$ belongs to $\{1\} \cup [5, \infty)$. These are all the natural numbers satisfying the given condition.

Answer 3

For $n = 1$ is true, but for $n = 2,3,4$ is not. but for $n \geq 5$ is true.

Hence, the solution set is $\{1\}\cup[5,\infty)$.

Now we assume is true for $n = k$, that is

$2^k > k^2$, we will have to show that it is true for $n = k+1$.

$2^{k+1} = 2(2^k)$, but $2^k > k^2$ by induction hypothesis then $2^{k+1} > 2k^2 > k^2$.

Hence by the induction principle it is true for all $n \geq 5$ (also for $n = 1$).

Answer 4

(A rather informal approach, just for fun!)

As $n$ increases by one, the expression $2^n$ doubles.

As $n$ increases by one, the expression $n^2$ increases by the $(n+1)$st odd.

This is because $n^2$ becomes $(n+1)^2 = n^2 + (2n+1)$ where $2n+1$ is the $(n+1)$st odd.

Note that the expressions are equal when $n = 4$: $2^4 = 16 = 4^2$.

As $n$ increases by one, the left hand side doubles, which means adding $16$. But, the right hand side increases by the $(4+1)$th odd, i.e., the fifth odd, $9$, going from $4^2 = 16$ to $5^2 = 25$.

So, after being equal when $n=4$, the exponential expression increases by $16$ whereas the quadratic expression increases by $9$, which means the former is now greater than the latter. Moreover, each subsequent increase by one in $n$ is leading the left hand side to grow by twice as much as before, whereas the right hand side grows by two more than the previous iteration. This means that the exponential expression will continue to be greater than the quadratic expression for $n \geq 5$.

We already saw the inequality does not hold for $n = 4$, since both sides are equal, and so all that remains now is to check the earlier natural numbers:

When $n=1$, we have $2^1 = 2 > 1 = 1^2$; when $n=2$, we have equality; when $n = 3$, we have that $2^3 = 8 < 9 = 3^2$. Whether to include $0$ in $\mathbb{N}$ is a function of your course, but let us at least note for completeness that $2^0 = 1 > 0 = 0^2$.