0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you let us know what you have tried so that one can give you right direction $\endgroup$ – DSinghvi Nov 17 '14 at 10:02
  • $\begingroup$ It may be easier to prove this in the form $n^3\le 3^n$. $\endgroup$ – lhf Nov 17 '14 at 11:21
0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.