1
$\begingroup$

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

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

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – aBitwise Sep 25 '18 at 19:41
  • $\begingroup$ 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 $\endgroup$ – Ross Millikan Sep 25 '18 at 19:50
  • $\begingroup$ 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. $\endgroup$ – aBitwise Sep 25 '18 at 20:13
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Sep 25 '18 at 20:17
1
$\begingroup$

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

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

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

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

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.