Proving $n\leq3^{n/3}$ for $n\geq0$ via the Well-Ordering Principle [2]

Question

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.

Answer 1

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.

Answer 2

$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$

Answer 3

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