# Find all $n$ for which $2^n \ge (n+1)^2$

Find all of the elements of $X= \{ n \in \mathbb N: 2^n \ge (n+1)^2\}$

Could someone give me a hint to nudge me in the right direction?

-
Exponential growth is generally faster than polynomial (in this case quadratic) growth, as $n$ gets large. –  paw88789 Jul 26 '14 at 13:16
@paw88789 I am aware of that. However explicitly finding all the elements is somewhat more challenging –  Mathman Jul 26 '14 at 13:19

Find the smallest element $s$ in $X$ by hand. Then use induction to prove that for all $k\geq s$ : $k\in X\implies (k+1)\in X$.

-
I thought as much. However the fact $0 \in X$ put off –  Mathman Jul 26 '14 at 13:23
Ragnar: The smallest element is not $4$. $2^4 = 16 < (4+1)^2 = 25.$ It is true that $2^4 \geq 4^2$. Nor is the smallest element $5$, since $2^5 = 32 \lt (5+1)^2 = 36$. The smallest element such that $2^n \geq (n+1)^2$ will be $6$, since $2^6 = 64 \geq (6+1)^2 = 49$. So, Matthew, $X = \{n\in \mathbb N\mid n\geq 6\}.$ –  amWhy Jul 26 '14 at 13:40
Is there no option besides trial and error to get 6? What if the first integer for some other similar problem is 1000? –  BCLC Jul 26 '14 at 13:56
Thanks, Ragnar, for deleting your misleading, indeed, incorrect, follow-up comments. –  amWhy Jul 26 '14 at 13:57
@BCLC, then, you would have to (approximately) solve the equation $2^n=(n+1)^2$ and look for the smallest integer for which it is true. amWhy, missed the $+1$ for some reason. –  Ragnar Jul 26 '14 at 13:58

$\color{green}{2^0=1\ge(0+1)^2=1}$ ?*

$\color{red}{2^1=2\ge(1+1)^2=4}$ ?

$\color{red}{2^2=4\ge(2+1)^2=9}$ ?

$\color{red}{2^3=8\ge(3+1)^2=16}$ ?

$\color{red}{2^4=16\ge(4+1)^2=25}$ ?

$\color{red}{2^5=32\ge(5+1)^2=36}$ ?

$\color{green}{2^6=64\ge(6+1)^2=49}$ ?

$\color{green}{2^7=128\ge(7+1)^2=64}$ ?

$\color{green}{2^8=256\ge(8+1)^2=91}$ ?

$\color{green}{2^9=512\ge(9+1)^2=100}$ ?

...

*whether $0$ is considered natural or not is a matter of convention.

-
Is there no option besides trial and error to get 6? What if the first integer for some other similar problem is 1000? –  BCLC Jul 26 '14 at 13:56
Given the small values of the parameters, one can expect that the crossing point(s) will be quickly found. In this particular case, enumeration is quite effective: it avoids to drop corner cases and gives excellent insight on the function behaviors, with a minimal effort (takes less than a minute to list the powers and the squares). Of course, after the solution is found, it must be proved. –  Yves Daoust Jul 26 '14 at 14:35

It is interesting to find the values at which strict equality $2^n=(n+1)^2$ occurs, which may be real numbers.

This is a transcendental equation which cannot be solved analytically. Let us first take the square roots, to get a linear RHS: $$\sqrt2^n=n+1.$$ And let us derive to find extrema: $$\ln\sqrt2\ \sqrt2^n=1.$$ The single solution, $-\frac{\ln\ln\sqrt2}{\ln\sqrt2}$, lies between $3$ and $4$, so that $2^n-(n+1)^2$ decreases from $0$ (value $0$) to $3$ (value $-8$) then increases after $4$ (value $-9$). So there is a root at $n=0$, and another at some $n>4$.

At this stage, there is little better to do than trial and error with increasing $n$ values. Being pessimistic, we will use exponential search first, i.e. doublings of $n$. $$f(8)=175\ge0.$$ Now the solution is bracketed by $[4,8]$ and we will continue with dichotomic search: $$f(6)=15\ge0,$$ $$f(5)=-4<0.$$ And we are done, $X=[0]\cup[6,+\infty[$.

Assume now that we need to solve for $2^{n-1000}\ge(n+1)^2$ instead. Following the same procedure, we find that the function increases for $n\ge 1003$, $f(1003)=-1008008$.

Then $$f(2006)\gg0$$ $$f(1504)\gg0$$ $$f(1253)\gg0$$ $$f(1128)\gg0$$ $$f(1065)\gg0$$ $$f(1034)=17178797959\ge0$$ $$f(1018)=-776217<0$$ $$f(1026)=66054135\ge0$$ $$f(1022)=3147775\ge0$$ $$f(1020)=6135\ge0$$ $$f(1019)=-516112<0.$$

$X=[1020,+\infty[$.

(At some stage, switching to the secant method can be an advantage.)

-

Hint: You can prove by induction on $n$ that $2^n \geq n^2$ whenever $n\geq 4$. Then note that $(n+1)^2 = n^2 + 2n + 1$.

Edit: Just to keep the record straight, in reference to comments above, it is true that $Y = \{n \in \mathbb N\mid 2^n \geq m^2\} = \{n\in \mathbb N\mid n\geq 4\}$. However, to satisfy membership in the posted inequality, $$X = \{n \in \mathbb N\mid 2^n \geq (n+1)^2\}=\{n\in \mathbb N\mid 2^n \geq n^2 + 2n + 1\}$$ requires that $n \geq 6$. So we need to reject $4, 5$, since $2^4 = 16 \lt (4+1)^2 = 25$, and $2^5 = 32 \lt (5+1)^2 = 36$. So $2^n \geq (n+1)^2$ is a stricter requirement on $n \in \mathbb N$ than is $2^n \geq n^2$.

-