0

I have done easier induction proofs but I got stuck on this one. I start with checking the base case:

$$3^3 \leq 3^3$$ $$27 \leq 27$$

So the base case holds. Next I assume it works for $p+1$ and want to prove it for $p + 1$ and this is where I get stuck. I start by plugging in $p+1$ in the left side of the inequality:

$$(p+1)^3 = (p+1)(p+1)(p+1) = p^3 + 3p^2 + 3p + 1$$

but then I don't know what to do? I gave up and I checked my book and the next step is this:

$$(p+1)^3 = (p+1)(p+1)(p+1) = p^3 + 3p^2 + 3p + 1 ≤ p^3 +p^3 +p^2 +1$$

But where did p^3 +p^3 +p^2 +1 come from? I don't understand it. I want to reach the end where I can see that (p+1)^3 is indeed less than 3^(p+1) but I get stuck on "p^3 +p^3 +p^2 +1" because I have no idea where they got that from.

If someone could explain you would really make my day!

user5846939
  • 221
  • 1
    Is $p3+p3+p2+1$ supposed to say $p^3+p^3+p^2+1$? If so, then this is because $3p^2 \leq p\cdot p^2 =p^3$ (since the base case is $p=3$, so certainly $3 \leq p$). Similaly $3p \leq p\cdot p=p^2$. – kccu Apr 16 '17 at 18:38
  • Yes I was about to help edit, and I also wondered that part. – mathreadler Apr 16 '17 at 18:39
  • By the way welcome to the site. Please consider learning MathJax as it is used for typesetting math. It gets easier to read and increases chances of good responses to questions. – mathreadler Apr 16 '17 at 18:41

3 Answers3

1

This answer only explains the inequality

$$p^3 + 3p^2 + 3p + 1 ≤ p^3 +p^3 +p^2 +1$$

you said your book gives. I won't speculate on how they proceed from there to the full result and/or how you could have circumvented using this inequality altogether. (See some of the other answers for more on that last point.)

What they do is for each term on the left find a term (on the right) that is at least as big. So we really have 4 inequalities:

$$p^3 \leq p^3$$ $$3p^2 \leq p^3$$ $$3p \leq p^2$$ $$1 \leq 1$$

I guess the outermost two are obvious. To see why the other two hold, remember that $p^3 = p \cdot p^2$ and $p^2 = p \cdot p$.

UPDATE: the above explains why the inequality is true, but it dawned on me that perhaps your question is how they came up with the terms on the right hand site in the first place.

The answer is: they want, on the right hand side terms that 'look like' $p^3$ because $p^3$ is something they can handle. The reason for that is that the Induction Hypothesis tells us that $p^3 \leq 3^p$, so applying the IH takes us finally away from the world of $p^\textrm{something}$ to the desired world of $3^{\textrm{some expression in } p}$.

But in order to do that, we need our $p^\textrm{something}$ to be in the specific form $p^3$.

Hence replacing two out of four of the annoying terms on the left hand side by the more beloved (because appearing in the IH) $p^3$ is already pretty good. And I speculate that their next move will be to note that $p^2 + 1 \leq p^3$ (for $p \geq 3$)so that we can write:

[all the previous stuff] $\leq p^3 + p^3 + p^3$.

Now we are in a position to apply the Induction Hypothesis to obtain

[everything we talked about so far] $\leq 3^p + 3^p + 3^p$,

from which it is only a small step to the final answer.

Vincent
  • 10,614
  • What? But the right side of the inequality only says 3^n. So why isn't the right side only 3^(p+1)? I dont understand what you mean with they just find a term. Where do they get p^3 + p^3 + p^2 + 1 from? – user5846939 Apr 16 '17 at 19:11
  • @user5846939 I am solely talking about the in equality at the top of this answer: the one you said you got stuck on when reading your book. When I say left or right hand side I mean the left and right hand side of that inequality, not of the more interesting inequality n^3 \leq 3^n$. So both the left hand side and the right hand side have 4 terms and the truth of the inequality follows from the fact that the first on the left is smaller/equal than the first on the right, the second on the left is smaller/equal than the second on the right etc. – Vincent Apr 17 '17 at 20:36
  • @user5846939 I updated my answer to include some stuff on what I believe was going on in the minds of the people who wrote your book. I hope this helps – Vincent Apr 17 '17 at 21:59
0

you must show that from $$n^3\le 3^n$$ follows $$(n+1)^3\le 3^{n+1}$$ multiplying the inequality $$n^3\le 3^n$$ by $3$ we get $$3n^3\le 3^{n+1}$$ but we have $$(n+1)^3=n^3+3n^2+3n+1\le 3n^3$$ if $$2n^3-3n^2-3n-1\geq 0$$ for $$n\geq 3$$

Dr. Sonnhard Graubner
  • 95,283
0

Since $\frac{n+1}{n}$ is stricly decreasing for $n\ge 3$, we have $$(\frac{n+1}{n})^3\le (\frac{4}{3})^3<3$$ for $n\ge 3$.

Hence we have , if we assume $n^3\le3^n$ : $$(n+1)^3<3n^3\le3\cdot 3^n=3^{n+1}$$ As an additional result, we have $n^3<3^n$ for $n\ge 4$

Peter
  • 84,454