Use strong induction to prove that $n\leq3^{n/3}$ for every integer $n\geq0$

Question

Use strong induction to prove that $n\leq3^{n/3}$ for every integer $n\geq0$

According to steps of Strong Induction,
1) I assume the predicate as $P(n)$:
$n\leq3^{n/3}$ for every integer $n\geq0$

2) Check the base case $P(0)$ is true, then apply induction on $n$, assume that $P(n)$ holds for integers from $0$ to $n$.

3) Then I need to prove $P(n+1)$ also holds to prove the predicate holds for all integer $n\geq0$.

But I am in trouble on step 3, I found that the induction on $n$ doesn't have any help to prove $P(n+1)$. I think there must be another helpful induction on $n$, but I can't figure it out. Please help, thanks.

Answer 1

Start by proving $P\left(0\right),P\left(1\right),P\left(2\right),P\left(3\right)$ and $P\left(4\right)$.

Then for $n\geq4$ we have by strong induction: $$3^{\frac{n+1}{3}}=3.3^{\frac{n-2}{3}}\geq3\left(n-2\right)=n+1+\left(2n-7\right)\geq n+1$$

Answer 2

You can first note that for $n \geq 3$, we have

$$ 1 + \frac{1}{n} \leq 1 + \frac{1}{3} = \frac{4}{3} \leq 3^{1/3}$$

Assume $n \leq 3^{n/3}$ is true for some $n \geq 3$.

Then $3^{(n+1)/3} \geq 3^{1/3}n \geq (1 + \frac{1}{n})n = n+1$.

Answer 3

If $3^{\frac m3}\ge m, 3^{\frac{m+1}3}=\sqrt[3]3\cdot3^{\frac m3}\ge \sqrt[3]3m$

It sufficient to show $\sqrt[3]3m\ge m+1\iff3m^3\ge(m+1)^3\iff\left(1+\dfrac1m\right)^3\le3 $

Now $\left(1+\dfrac1m\right)^3>\left(1+\dfrac1n\right)^3$ if $n>m$

and $\left(1+\dfrac1m\right)^3<3$ if $m\ge3$

Answer 4

the trick in the thrid step is to use P(n) to show P(n+1). For your example that means

$P(n+1): n+1 \leq 3^{(\frac{n+1}{3})}=\sqrt[3]{3}3^{(\frac{n}{3})}$

$\Leftrightarrow \sqrt[-3]{3}(n+1)\leq 3^{(\frac{n}{3})}$

Now is the time where you can insert P(n).

$ \sqrt[-3]{3}(n+1)\leq n \Leftrightarrow 1\leq \sqrt[3]{3}n -n$

This is True for $n\geq3$. Step 3 is complete.

Cheers