<s>[INST] 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.
 [/INST] 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
</s>