Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

4 Answers 4

up vote 3 down vote accepted

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$.

share|improve this answer
    
I thought as much. However the fact $0 \in X$ put off –  Mathman Jul 26 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 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 at 13:56
    
Thanks, Ragnar, for deleting your misleading, indeed, incorrect, follow-up comments. –  amWhy Jul 26 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 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.

share|improve this answer
    
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 at 13:56
1  
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 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.)

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.