Strong induction - prove that $n \le 3^\frac{n}3$ for every integer $n \ge 0$.

Question

This question was asked somewhere else, but I am having trouble with the algebra in the inductive step. And if you don't mind, let me know if anything else seems blatantly wrong as well.

So far I have :

Assume the predicate $P(n)$, where $n \le 3^\frac{n}3$. We will prove this is true for every $n\ge 0$ via strong induction. Basis: $P(0)= 0 \le 1$, $P(1)= 1\le 3^\frac13$, $P(2)= 2\le3^\frac23$, $P(3)= 3=3$ holds for first four numbers

Inductive Step: Let $n=k$. Assume that $P(k)$ is true where $k$ is $3 \le i \le k$ and $i$ being some integer less than $k$. We will prove this also holds for the $k+1$ case: $4 + 5 + ... + k + (k+1) \le 3^\frac{k+1}3$.

Using algebra: $-(k+1) \le 3^\frac13 * 3^\frac{k}3$
$-3^{-\frac13}*(k+1) \le 3^\frac{k}3$
$-3^{-\frac13}*(k+1) \le k$ (substituting $P(k)$ back in)
stuck here...

Answer 1

Assume you know it is true up to $k$. For $k \ge 4$ we have $$3^{\frac {k+1}3}=3\cdot 3^{\frac {k-2}3}\ge 3\cdot (k-2)\gt k+1$$

Answer 2

Hint: I would prove that $$n^3\le 3^n$$ then we have to Show that $$(n+1)^3\le 3^{n+1}$$ Multiplying the first inequality by $3$ we get $$3^{n+1}\geq 3n^3\geq (n+1)^3$$

Answer 3

It is clear for $n = 1,2,3,4$. (Base cases). Assume it is true for $n$, now notice that \begin{equation} n+1\leq 3^{\frac{n}{3}} + 1 = 3^{-\frac{1}{3}}3^{\frac{n+1}{3}} + 1 \end{equation} But the function $f(x) = 3^{-\frac{1}{3}}x + 1 \leq x$ for $x \in [x_0,\infty]$ where $x_0 = \frac{1}{1-3^{-\frac{1}{3}}} \simeq 3.2612$. So we have proved it for $n \geq 4$.