Is $3^n>2^n n^3$ as n approaches infinity? Or is the opposite true?

Question

My teachers are having a debate regarding this inequality. One of them used a limit to try to prove that $3^n>2^n n^3$ is in fact true, $$\begin{equation}\begin{aligned} \lim_{n \to \infty}\frac{3^n}{2^n n^3} &= \lim_{n \to \infty}(\frac{3}{2})^n \space\frac{1}{n^3} \\ &= \lim_{n \to \infty}\frac{1.5^n}{n^3}\\ &= \infty \\ \end{aligned}\end{equation}$$

Is this a valid proof?

Answer 1

Yes, as n approaches $\infty$, this equation holds true:

If $3^n > 2^nn^3$ were to false, $3^n < 2^nn^3$ would be true. Simplifying this gives:

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

At the previous step, there is an identity when taking the limit of n to $\infty$: $\lim{_{n \to \infty}}, n^\frac{1}{n} \to 1$ $$(\frac{3}{2})^{\frac{1}{3}} < 1$$ This is clearly wrong and therefore, if we reversed the inequality, it would be true, proving that $$\lim{_{n \to \infty}}: 3^n > 2^nn^3$$.

Note: This only works if n approaches $\infty$ (for large n values only). I keyed this function in binary search program and found that it if the values for n were restricted to $\mathbb N$, the lowest value would be 24, for this equation to hold true.

$\therefore n >= 24$

Answer 2

Here is a combinatorial proof of the inequality.

Let us look at functions from the set $A=\lbrace 1,2,3,\cdots,n\rbrace$ to the set $B=\lbrace 0,1,2 \rbrace$. There are $3^n$ such functions. Now, we can separate these functions into parts $F_k$ where $F_k=\lbrace f: |f^{-1}(2)|=k \rbrace$ and $B^A= \cup^{n}_{k=0} F_k$ (disjoint union). Let us try to calculate $|F_k|$. We can choose the set of elements in $a\in A$ such that $f(a)=2$ in $^nC_k$ ways. The rest of the elements can be assigned values in $2^{n-k}$ ways. So, $|F_k|=2^{n-k}\times ^nC_k$.

Now, make the following observation. $|F_k|>|F_{k-1}|$ for large enough $n$. Why? Because $^nC_k$ is a polynomial in $n$ of degree $k$ and therefore, will outgrow the polynomial $^nC_{k-1}$ of degree $k-1$. This can also be shown combinatorially but this is just easier.

$3^n=|B^A|> \Sigma_{k=3}^{28} |F_k|> 24|F_3|+|F_3|= 24\times2^{n-3}\times \frac{n(n-1)(n-2)}{6}+|F_3|= 2^n(n^3 -3n^2+3n)+ |F_3|> 2^nn^3$ for large enough $n$. This was to be shown.