Proving $n\leq3^{n/3}$ for $n\geq0$ via the Well-Ordering Principle [2] I know this question was already asked in here, but it was never marked as answered and all the solutions base themselves on the fact that $3(m-1)^3 < m$, what comes from assuming $3^m < m$ and it's not clear to me.
I tried multiple ways to understand why this assumption was made, but I can't figure it out. My first assumption was that since $m \in S$ it's true that:
$m > 3^{m/3}$
and by consequence:
$m^3 > 3^{m}$
but it still does not prove $3^m < m$. Any help is very appreciated.
 A: The well ordering principle comes into play in trying to find the first $n$ where $n^3 > 3^n$.
We know $1^3 < 3^1$.
But can there be any $n^3 > 3^n$?
If so, there must be a first $n$ where $n^3 > 3^n$. But if $n$ is the first then it must be that  $(n-1)^3 \le 3^{n-1}$.
Now hopefully we will be able to show $(n-1)^3 \le 3^{n-1}$ while $n^3 > 3^n$ can't ever happen which means we can never have a first case where $k^3 \le 3^k$ is not true, which means $k^3 \le 3^k$ always will be true.
So multiplying both sides by $3$ we have$3(n-1)^3 \le 3^n$. But we also have $3^n < n^3$.  So $3(n-1)^3 \le 3^n < n^3$.
And $3(n^3 - 3n^2 + 3n -1) < n^3$.
Well now simplify that and
$2n^3 - 9n^2 + 9n - 3< 0$ so
$2n^3 +9n < 9n^2 + 3$.
$2n + \frac 9n < 9 + \frac 3{n^2}$.
So $2n < 2n + \frac 9n < 9 + \frac 3{n^2} $.
If $n \ge 2$ then $\frac 3{n^2} < 1$ and so we either have $n =1$ or $2n < 9+\frac 3{n^2}< 9+1 = 10$.  In any event we must have $n < 5$ or in other words, $n=1,2,3,$ or $4$.
So we test that $n=1,2,3,4$ and get $1^3 < 3^1; 2^3 =8 < 9 =3^2; 3^3 = 3^3; 4^3=64 < 81 = 3^4$.  so none of those are the first exception.
So the first exception can not exist.
And if there can't be a first value, there can't be any value.
A: $n\le 3^{n/3}$ is true for $n=1$ because $\sqrt[3]{3}>1$
It is true for $n=2$, too, because $\sqrt[3]{3^2}\approx 2.08>2$
Now suppose that $3^{n/3}\ge n$ is true for $n$ and let's prove it for $n+1$
$3^{(n+1)/3}=3^{n/3}\cdot \sqrt[3]{3}\ge \sqrt[3]{3}n>n+1$. Proved.
$\sqrt[3]{3}n>n+1$ because $\sqrt[3]{3}n-n\approx 0.44n>1$ for any $n>2$
A: I already accepted @fleablood's answer. I'd just like to share my own proof after some work on it as further reference for other people working on this problem.
Theorem: $n \leq 3^{n/3}\text{ for }n \geq 0$
Proof:
Let C be the set of counterexamples to the theorem, namely
$$C ::= \{n \in \mathbb{N} | n > 3^{\frac{n}{3}}\}$$
For the purpose of a contradiction, assume $C$ is not empty. By the Well-ordering principle, there's a least element, $c \in C$. The $c$ element can't be:

*

*1, because $1<3^\frac{1}{3}$;

*2, because $2<3^\frac{2}{3}$;

*3, because $3=3^\frac{3}{3}$;

*4, because $4<4^\frac{4}{3}$.

Therefore, $c>4$.
If $c$ is the least counterexample for the theorem, $c-1$ must hold true, once it's less than $c$ itself. So:
$$
c-1 \leq 3^\frac{c-1}{3}\\
c-1^3 \leq 3^{c-1}\\
c-1^3 \leq (3^c)(3^{-1})\\
c-1^3 \leq \frac{3^c}{3}\\
3(c-1)^3 \leq 3^c\\
$$
$c \in C$, therefore, $c > 3^{\frac{c}{3}}$:
$$
c > 3^{\frac{c}{3}}\\
c^3 > 3^c\\
3^c < c^3
$$
So, we can state that $3(c-1)^3 \leq 3^c < c^3$ and that $3(c-1)^3 < c^3$. Now, by manipulation:
$$
3(c-1)^3 < c^3\\
3(c^3-3c^2+3c-1) < c^3\\
3c^3-9c^2+9c-3 < c^3\\
2c^3-9c^2+9c-3 < 0\\
2c^3+9c < 9c^2+3\\
$$
Dividing both sides by $c^2$, we get:
$$
2c+\frac{9}{c}<9+\frac{3}{c^2}\\
$$
As stated  before, $c>4$, so:
$$
c>4\\
c^2>16\\
\frac{1}{c^2}<\frac{1}{16}\\
\frac{3}{c^2}<\frac{3}{16}\\
9+\frac{3}{c^2}<9+\frac{3}{16}\\
9+\frac{3}{c^2}<9.1875<10\\
9+\frac{3}{c^2}<10
$$
Back to the main inequality:
$$
2c+\frac{9}{c}<9+\frac{3}{c^2}<10\\
$$
Since $c \in \mathbb{N}$, we can assume $2c < 2c+\frac{9}{c}$:
$$
2c<2c+\frac{9}{c}<9+\frac{3}{c^2}<10\\
2c<10\\
c<5
$$
$c \in \mathbb{N}$, $c>4$ and $c<5$ is a contradiction and therefore $C$ must be empty. The theorem is true.
QED
