0

Prove by mathematical induction that

$$\forall n \geq 4 \in \mathbb{N}: 3n^2 + 3n +1 < 2(3^n)$$

Step 1: Show that the statement is true for n = 4:

$$3(4)^2 + 3(4) +1 < 2(3^4)$$

Which simplifies to $61 < 162$. That completes the base case.

Step 2: Show that if the statement is true for $n = p$, it is true for $n = p + 1$:

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

All that is required now is to show that $6p + 6 \leq 4(3^p)$ since $2(3^{p+1}) = 6(3^p)$. Does this require another proof by mathematical induction or is it sufficiently rigorous to say something like "well, $x^p$ clearly grows faster than $px$ as $p$ approaches infinity, so the inequality is trivial"?

In a larger context, are there any specific rules for when inequalities can be considered trivial?

MathInferno
  • 1,186
  • Consider using the property for $n=p$ again. – Demosthene Mar 14 '15 at 21:52
  • You mean that since $2(2(3^p))$ is larger than 2($3n^2+3n+1)$, then it should also be larger than 6p + 6? – MathInferno Mar 14 '15 at 21:55
  • @MathInferno Yeah, that's basically what CuddlyCuttlefish showed. For $p>4$, you have $p^2>p$, therefore $2(3p^2+3p+1)>2(3p+3p+1)=12p+2>6p+6$. Or something like that. (As you said, it is quite trivial). – Demosthene Mar 14 '15 at 22:33

1 Answers1

1

By the inductive hypothesis, we assume that this statement is true:

$$3n^2 + 3n + 1 < 2(3^n)$$

$$3(n+1)^2 + 3(n+1) + 1 = 3n^2 + 9n + 7$$

From the inductive hypothesis:

$$3n^2 + 3n + 1 +6n+6 < 2(3^n)+6n+6$$ $$3(n+1)^2 + 3(n+1) + 1 < 2(3^n)+6n+6$$

So it will suffice to show:

$$2(3^n)+6n+6 < 2(3^{n+1}) = 6(3^n)$$ $$2(3^n)+6n+6 < 2(3^{n+1}) = 6(3^n)$$ $$6n+6 < 4(3^n)$$

Return to the inductive hypothesis:

$$6n^2 + 6n + 2 < 4(3^n)$$

As $6n^2$ is strictly increasing in our domain, and $6(4)^2 = 96 > 4$, we can replace it: $$4 + 6n + 2 < 6n^2+6n+2 < 4(3^n)$$ $$6n + 6 < 4(3^n)$$ And so we are done.