Prove by induction that $3n^2 + 3n + 1 \leq 2(3^n)$

Question

This is a proof within another proof but I am stuck on the last few steps of: Prove by induction that $3n^2 + 3n + 1 \leq 2(3^n)$. Any help with good explanation would be wonderful!!! Here's what I've tried: Need to show: 3(n+1)^2 + 3(n+1) + 1 <= 2(3^(n+1))
= 3n^2 + 9n + 7
= 3n^2 + 3n + 1 + 6n + 6
<= 2(3^n) + 6n + 6 (By inductive Hypoth.)

Answer 1

Let $n=4$. You have then $3n^2 + 3n + 1 = 3\cdot 16 + 3\cdot 4 + 1 = 48 + 12 + 1 = 61 < 162 = 2\cdot 81 = 2\cdot 3^4 = 2\cdot 3^n$

So, our base case is true.

Suppose for our inductive hypothesis that $3n^2+3n+1 \leq 2\cdot 3^n$ for some $n\geq 4$.

You have then: $3(n+1)^2 + 3(n+1)+1 = 3n^2 + 6n + 3 + 3n + 3 + 1 = (3n^2+3n+1) + (6n+6)~~~(\dagger)$

Since $n\geq 4$ you have $6n+6 = 3\cdot 2\cdot n + 5 + 1 < 3\cdot n\cdot n + 3n + 1=3n^2+3n+1$

So, continuing from $(\dagger)$ you have:

$(3n^2+3n+1)+(6n+6) \leq (3n^2+3n+1)+(3n^2+3n+1)=2\cdot (3n^2+3n+1)$

$\leq^{IH}2\cdot (2\cdot 3^n)\leq 3\cdot (2\cdot 3^n) = 2\cdot 3^{n+1}$

This shows that $(3n^2+3n+1\leq 2\cdot 3^n)\wedge (n\geq 4)\Rightarrow (3(n+1)^2+3(n+1)+1\leq 2\cdot 3^{n+1})$, proving the claim for all $n\geq 4$ by induction.

---

The big trick here is to use the fact that $n\geq 4$ to your advantage to compare items of lower order with items of higher order that more easily combine.