Prove $2^n > a\cdot n^2$, for some $n \in \mathbb{N}$. ($a$ is a constant in $\mathbb{R^+}$)

Question

Suppose $a \in \mathbb{R^+}$. I need to prove $\exists n \in \mathbb{N}, 2^n > a\cdot n^2$.

Both L'Hôpital's rule and Lambert's W function are NOT allowed to use other than inequality or taking logarithm. I understand there is a classical induction proof for $2^n > n^2$, but this one seems to be tricky because of the constant $a$.

I have tried several approaches, but I cannot seem to figure out a $n$ (which most likely involves $max()$, $\lceil\rceil$). One approach I tried was to take $n = \lceil n_0 + log_2a\rceil$, where $n_0 \in \mathbb{R^+}$. But I cannot seem to prove that \begin{equation} 2^{n - log_2a} > n^2 \end{equation}

Am I on the right track or totally off? Can someone show please help with this proof? It has been bugging me for a while. Thanks in advance!

Answer 1

$2^{n}=(1+1)^{n}$. By Binomial Theorem we see that $2^{n} >1+n+\frac {n(n-1)} 2$. I will leave it to you to find out how large $n$ should be for $1+n+\frac {n(n-1)} 2 >an^{2} $.

Answer 2

Consider the function $f(x)=\dfrac{2^x}{x^2}$. It is obvious that it is an increasing function and tends to infinity for $x\ge1$. Therefore, given a constant $a$, we must find a $N$ that for any positive integer $n\ge N$, $\dfrac{2^n}{n^2}> a$, which means $2^n>a\times n^2$

Answer 3

Note that $$\lim_{x\to \infty} {2^x\over x^2}=\infty$$therefore ${2^x\over x^2}$ can be arbitrarily greater than any real number.

Answer 4

How about proving like this?

Since $\lceil a \rceil n^2 \ge an^2$, we only have to prove that $\exists n \in \mathbb{N}(2^n > mn^2)$ when $m \in \mathbb{N}$. Let us define the forward difference $\Delta f\colon \mathbb{N} \to \mathbb{Z}$ of a function $f\colon \mathbb{N} \to \mathbb{Z}$ as this: $$\Delta f(n) := f(n + 1) - f(n)$$ Simple observation shows that for a polynomial function $P$, the forward difference of it is also a polynomial function of degree one lesser than $P$. By induction, we can see that if we apply forward difference sufficiently many times, it will eventually become a constant function.

And now we prove a proposition to utilize this.

Proposition: For two functions $f, g\colon \mathbb{N} \to \mathbb{Z}$, if there exists $M \in \mathbb{N}$ such that $\Delta f(n) > \Delta g(n)$ for all natural number $n \ge M$, there exists $N \in \mathbb{N}$ such that $f(n) > g(n)$ for all natural number $n \ge N$.

Proof: If $f(M) \ge g(M)$, it is trivial. Namely, set $N = M + 1$. So let's assume that $f(M) < g(M)$. Let $k = g(M) - f(M) \in \mathbb{N}$. Since $\Delta f(n) > \Delta g(n)$ for all natural number $n \ge M$, $\Delta f(n) - \Delta g(n) \ge 1$ for all natural number $n \ge M$.

So $$g(M) = f(M) + k \le f(M) + \sum_{i = 0}^{i = k - 1} \{\Delta f(M + i) - \Delta g(M + i)\} = f(M + k) - \sum_{i = 0}^{i = k - 1} \Delta g(M + i)$$ Then $$f(M + k) \ge g(M) + \sum_{i = 0}^{i = k - 1} \Delta g(M + i) = g(M + k)$$ So we can set $N = M + k + 1$. $\blacksquare$

This proposition means that to prove the above proposition, it is sufficient to apply forward difference to both sides. Forward difference of $f(n) = 2^n$ is itself, but $g(n) = mn^2$ eventually becomes a constant function, but $2^l > l$ for all $l \in \mathbb{N}$, so it is done. Note that this method can be applied to arbitrary polynomials!

Answer 5

I understand there is a classical induction proof for $2^n>n^2$, but this one seems to be tricky because of the constant $a$

This can be easily proven by using the case $a=1$, where you already know the result is true for all large $n$.

Let $a$ be an arbitrary, fixed number, and we are looking to prove that we can find $n$ such that $2^n > a n^2$. We will make many assumptions on $n$ to simplify the problem. This is allowed because we are only looking for one $n$.

Choose $n=2k$ even, then it is enough to find one $k$ such that $$ 2^{2k} > 4ak^2.$$

Since $a$ is a fixed number, for every $k>2\sqrt a$, we have $k^2> 4a$. This means that it is enough to find $k>2\sqrt a$ such that $$ 2^{2k} > k^4$$ take square-roots: $$ 2^k > k^2$$ but we know by induction that this is true for all $k>4$, hence the result: any $k$ such that $k>4$ and $k> 2\sqrt a$ will do. Example: if $a=100$, then we predict that we can use any $k>20$, i.e. any $n=2k>40$. And sure enough, $2^{41} - 100 (41)^2 = 2199023087452 > 0$, which validates our claim.

Alternatively, here is the proof "the right way round". Let $a$ be arbitrary and fixed. we know that $2^k > k^2$ for any $k>4.$ Square both sides: we get $2^{2k}>k^4$. Now we just need to find $k>4$ such that $k^4 > a(2k)^2 = 4ak^2$. Solving this inequality gives $k>2\sqrt a$. This proves that if $k>2\sqrt a$ and $k>4$, then $n=2k$ solves $$ 2^n > a n^2,$$ QED.