Proving $n \leq 3^{n/3}$ for $n \geq 0$ via the Well-Ordering Principle

Question

I'm attempting to prove: $$n \leq 3^{n/3} \quad \text{for }n \geq 0$$

I'm having a little trouble continuing. This is what I have so far:

Suppose for a contradiction there is a subset of nonnegative integers $S$ such that $x > 3^{x/3}$ for $x \in S$. By the Well-Ordering Principle, there is some least element $m \in S$. It also means that for some $n < m$, $n \leq 3^{n/3}$ must apply, and since $n = 0$ holds we can conclude that $m > 0$. If follows that $m - 1 \geq 0$ and so $m - 1 \leq 3^{(m-1)/3}$ applies:

$$ \begin{align} m - 1 \leq 3^{(m-1)/3} &\equiv (m-1)^3 \leq 3^{m-1} \\ &\equiv 3(m-1)^3 \leq 3^m \\ &\equiv 3(m-1)^3 \leq 3^m < m \\ &\equiv 3(m-1)^3 < m \end{align} $$

But I'm not sure how to show now that this is a contradiction. How do I continue?

Answer 1

From $3(m-1)^3 < m$ we get $3m^3-9m^2+8m-3 < 0$ or $m(3m^2-9m+8) < 3 $ or $m(3m(m-3)+8) < 3 $.

This is false for $m \ge 4$ since $3m(m-3) \ge 3m \ge 12$. It is also false for $m=3$ by direct computation.

For a more general non-inductive proof, you can use the fact that $x^{1/x}$ is decreasing for $x \ge e$ so $e \le a < b$ implies that $a^{1/a} > b^{1/b}$ or $a^b > b^a$ or $a^{b/a} > b$.

Now put $a = 3$.

Answer 2

By some explicit calculation, you can see that the inequality holds for $m \leq 2$ which means that that the minimum value of that set of contradictions, $m$ has to be greater than 2.

$3(m-1)^{3} < m$, which is implied by your original assumption does not hold for any $m \geq 2$. There is the contradiction

Answer 3

Using contradiction, if there exist a $n \ge 0 $ such that

$$ \begin{align} n &> 3^{n/3} \end{align} $$

Then, because of the WOP, there will be a $n=m$ which is the least value of the set that satisfies the inequality above.

It is verifiable that $n \le 3^{n/3}$ holds true for $0 \le n \le 4$. Thus, $m \ge 5$

since $m-3 \lt m$

$$ \begin{align} (m-3) &\le 3^{(m-3)/3} \end{align} $$

Thus, $$ \begin{align} (m-3) &\le 3^{m/3}\cdot3^{-1}\\ 3(m-3) &\le 3^{m/3} \end{align} $$

It is known that $m \lt 3(m-3)$ for any $m \ge 5$, thus

$$ \begin{align} m \lt 3(m-3) &\le 3^{m/3}\\ m &\lt 3^{m/3} \end{align} $$

Which contradicts the premise $n > 3^{n/3}$.

Answer 4

Let C be the set C ::= {$ n \in N | n > 3^{n/3} $}

For the purpose of obtaining contradiction we assume that C is not empty

There is the smallest element $n_0 \in C$

$n_0 \geq 4$ since for n = 3 property holds

We have : $n_0 - 1 \leq 3^{{(n_0 - 1)}/3}$

$3(n_0 - 1)^3 \leq 3^{n_0} < n_0^3$

Draw the graph of the equation : $3(n_0 - 1)^3 - n_0^3= 0$. We have that for all $n \geq 4$ $3(n_0 - 1)^3 - n_0^3 > 0 $

$->$ contradicting the fact so C is empty.