Infimum $\frac{(n+1)^2}{2^n} $

Question

I need to find infimum $\frac{(n+1)^2}{2^n}$. Candidate is $ 0$. The first part of infimum definition is clear. I don't understand how to find $N(\varepsilon)$: $$\frac{(n+1)^2}{2^n}<\varepsilon+0$$ Maybe I can make some upper estimate but my attempts here were not successful.

Answer 1

Prove by induction that for $n$ large enough (say $n>10$), you have $2^n>(n+1)^3$, then write

$$\frac{(n+1)^2}{2^n}<\frac{(n+1)^2}{(n+1)^3}=\frac{1}{n+1}<\epsilon$$

if $n>\max\left\{1+\frac{1}{\epsilon},10\right\}$

$\\$

EDIT: Details of the proof by induction of $2^n>(n+1)^3$

Base Case: For $n=11$ we have $2048>1728$ which is true.

Induction step: If $2^{n-1}>n^3$ then $2^n=2\cdot 2^{n-1}>2n^3>(n+1)^3$

The last inequality is equivalent to $\left(1+\frac{1}{n}\right)^3<2$ which is equivalent to $n>\frac{1}{\sqrt[3] 2-1}\approx 3.84$, which is obviously true when $n>10$

Answer 2

HINT: Suppose that you knew that $(n+1)^2<2^{n/2}$; then you’d have

$$\frac{(n+1)^2}{2^n}<\frac{2^{n/2}}{2^n}=\frac1{2^{n/2}}\;,$$

and $\frac1{2^{n/2}}$ can certainly be made as small as you like.

Of course $(n+1)^2$ isn’t less than $2^{n/2}=\left(\sqrt2\right)^n$ when $n$ is fairly small, but you know that an exponential with a base greater than $1$ grows faster than any polynomial, so you know that $(n+1)^2<2^{n/2}$ for all sufficiently large $n$. To finish the argument, you just have to work out what sufficiently large is in this case. And you don’t have to hit the nail right on the head. For instance, you might note that $21^2=441<1024=2^{10}$, so that $(n+1)^2<2^{n/2}$ when $n=20$. Now show by induction on $n$ that $(n+1)^2<2^{n/2}$ for all $n\ge 20$.

Answer 3

[An alternative to the $\epsilon-N$ approach] The function $f(x)=\frac{(x+1)^2}{2^x}$ has limit $0$ when $x\to+\infty$; $$ \lim_{x\to\infty}\frac{(x+1)^2}{2^x}\overset{L'H}{=}\lim_{x\to\infty}\frac{2(x+1)}{\log (2)2^x}\overset{L'H}{=}\lim_{x\to\infty}\frac{2}{\log(2)^22^x}=0. $$