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

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

• "This question was asked somewhere else" could you maybe provide a link to the original? – Surb Sep 25 '18 at 19:28
• Sorry, it was ask here, but i was still a little confused. math.stackexchange.com/questions/1025734/… – aBitwise Sep 25 '18 at 19:33

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

• I still a little unsure of your reasoning for this. So, you split 3^((k+1)/3) up into 3 * 3^((k-2)/3) and set it greater than equal to 3 * (k-2). Why? – aBitwise Sep 25 '18 at 19:41
• In an induction proof you want to relate the new case to an old one that has been proven. The first step brings in the same expression for $k-2$ which we assume has already been proven. The second step makes use of what has been proven. I think this answer is a great discussion – Ross Millikan Sep 25 '18 at 19:50
• Ahh, I see. In strong induction, we assume two things. For this example k, but also all its predecessors. I think I understand. Appreciate the link as well, definitely will give it a read. – aBitwise Sep 25 '18 at 20:13
• Yes, that is the difference between strong induction and normal induction. In this case we really have three chains going upward, one for numbers $0 \bmod 3$, one for $1 \bmod 3$ and one for $2 \bmod 3$. We could formulate it as normal induction for each of those. We could also do normal induction by splitting off a factor $\sqrt[3]3$ instead of a factor $3$. There are many routes to the solution here. – Ross Millikan Sep 25 '18 at 20:17

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

• So you think that $3 = 3\times1^3 \ge (1+1)^3 = 8$? – gammatester Sep 25 '18 at 19:31
• All examples for which this inequality not hold can you check, for all other numbers this inequality is true. – Dr. Sonnhard Graubner Sep 25 '18 at 19:34
• So we have $$3n^3\geq (n+1)^3$$ if $$n(\sqrt[3]{3}-1)\geq 1$$ this is $$n\geq \frac{1}{\sqrt[3]{3}-1}$$ – Dr. Sonnhard Graubner Sep 25 '18 at 19:36
• Every induction prove must NOT start for $n=1$!!!! – Dr. Sonnhard Graubner Sep 25 '18 at 19:43
• The answer of Dr. SG is a Hint. It is clearly written there. A hint has not to contain all details. – user376343 Sep 25 '18 at 21:21

It is clear for $$n = 1,2,3,4$$. (Base cases). Assume it is true for $$n$$, now notice that $$$$n+1\leq 3^{\frac{n}{3}} + 1 = 3^{-\frac{1}{3}}3^{\frac{n+1}{3}} + 1$$$$ 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$$.

• how do you find $x_0$? – Surb Sep 25 '18 at 19:30
• Find the intersection $3^{-\frac{1}{3}}x + 1 = x$ and solve for $x$. @Surb – Ahmad Bazzi Sep 25 '18 at 19:31
• How did you get 3^(n/3) + 1 in the first part? Shouldn't it just be 3^((n+1)/3)? – aBitwise Sep 25 '18 at 19:43
• By induction hypothesis, you have that $n \leq 3^{n/3}$. So just add $1$ on both sides. – Ahmad Bazzi Sep 25 '18 at 19:52