I do not understand this particular step in a proof using the Well Ordering Principle

Question

Below is a proof using the Well Ordering Principle. I get lost starting at $(13)$...

$$ \begin{aligned} P(c): &:=c^{3} \leq 3^{c} \\ & \equiv c^{3} \leq 3(c-1)^{3} \\ & \equiv c \leq \sqrt[3]{3} \times(c-1) \end{aligned} $$

I don't understand how we get $c^{3} \leq 3(c-1)^{3}$ from $c^{3} \leq 3^{c}$.. why does the righthand side of the inequality change like that?

Answer 1

The whole thing is a rather appalling mess; I might have given it as much as $7$ points out of $10$ if it had come from a weak student. As Ross Millikan points out in the comments, $P(n)$ should be simply $n\le 3^{n/3}$; the statement given as $P(n)$ is not in fact a function of $n$ at all.

$C$ is apparently supposed to be the set of non-negative integers for which the proposition fails, the goal being to show that $C$ must be empty. What is actually ‘defined’ is something called $C(n)$ that apparently depends on $n$ and yet is defined as $\{n\in\Bbb N:n\ne 3^{n/3}\}$, something that does not depend on $n$ and is not what is wanted for $C$ anyway, since we’re not trying to prove that $n=3^{n/3}$ for all $n\in\Bbb N$.

Presumably $c$ is supposed to be the least element of $C$, not ‘the lesser’ element of $C$.

The two lines immediately below $(13)$ do not follow from $(13)$. The argument is probably intended to be that $c\le\sqrt[3]3(c-1)$, since $c-1\ge 4$, so $c^3\le 3(c-1)^3$, and $P(c)$ now follows from $(12)$.

Answer 2

The proof is in the reverse order of what it should be. They start from $P(c)$, which is what they want to prove and work to something we know. It should go the other way. We start with the claim that for $c \ge 4$ (they say $n$ but we are not talking about $n$ here) we have $c \le \sqrt[3]3(c-1)$, which is true but asserted without proof. We should say that for $c \ge 4$ we have $\frac c{c-1}\le \frac 43 \le \sqrt[3]3$, so $c \le \sqrt[3]3(c-1)$. We then go upward to $(13)$, which is what we want to prove.

Answer 3

You want to show that $c^3 \le 3^c$ by induction.

This means that you want to show that $(c-1)^3 \le 3^{c-1}$ implies that $c^3 \le 3^c$.

By the induction hypothesis, $3^c = 3\cdot 3^{c-1} \ge 3(c-1)^3 $.

Therefore, if you can show that $3(c-1)^3 \ge c^3 $ then $3^c \ge c^3 $.

Now we can proceed as above. Taking cube roots, $3(c-1)^3 \ge c^3 $ becomes $3^{1/3}(c-1) \ge c $ or $c(3^{1/3}-1) \ge 3^{1/3} $ or $c \ge \dfrac{3^{1/3}}{3^{1/3}-1} = \dfrac{1}{1-3^{-1/3}} \approx 3.26... $ so the induction will work for $c \ge 4$.

Since $4^3 (64) < 3^4 (81) $, $c^3 \le 3^c$ for $c \ge 4$. (With induction, you always have to check the base case.)

Answer 4

There's so much notational and organizational sloppiness to the given proof that it doesn't really convey a valid argument. A more clear, complete version would be something like:

Let $C=\{n\in \Bbb N:n^3>3^n\}$. We wish to show that $C$ is empty.

We proceed by contradition: suppose that $C$ is nonempty. Then by the well-ordering principle, $C$ has a smallest element $c$. Note the following:

1. Since $c\in C$, we have $c^3>3^c$.
2. Since $c$ is the smallest element of $C$, we know that $c-1\notin C$, so $(c-1)^3\le 3^{c-1}$.
3. We can verify directly that $n^3\le3^n$ for $n\in\{0,1,2,3\}$, so we must have $c\ge4$.

Combining these observations, we have $\left(\frac43\right)^3=(1+\frac1{4-1})^3\ge(1+\frac1{c-1})^3=(\frac c{c-1})^3=\frac {c^3}{(c-1)^3}>\frac{3^c}{3^{c-1}}=3$, i.e. $64>81$, which is false. Therefore our assumption that $C$ is nonempty must be false. In other words, every $n\in\Bbb N$ satisfies $n\le3^{n/3}$.