Solving an inequality induction

Question

For all: $$ n \ge 6, 4n^2+1 < 3*2^n $$

p(n): $ 4n^2+1 < 3*2^n $

My work:

Basis Step: P(6) 145 < 192 is true

Induction Step: Let $ n\ge 6 $, Assume $ 4(n+1)^2 +1 < 3*2^{n+1}$

What should I do next??

Answer 1

The next step is to assume it is true for $n$, that is $$4n^2+1<3∗2^n,$$ and use that to prove that it is true for $n+1$, that is $$4(n+1)^2+1<3∗2^{n+1}.$$

---

Hint: Notice that $$4n^2+1<3∗2^n \implies\frac{4n^2+1}{3*2^{n}}<1,$$ and $$4(n+1)^2+1<3∗2^{n+1}\iff \frac{4n^2+1}{3*2^{n}}+\frac{8n+4}{3*2^{n}}<2.$$

Answer 2

Base case: When $n=6$, we get $4\times 6^2+1 <3 \times 2^6 \iff 145<192$ which is right.

Inductive step: Assume that this ineqiality is true for when $n=k$, $\forall n\ge6$. To prove by induction, we want to show it's true for when $n=k+1$, and we are done.

So, when $n=k+1$, we get

$$ 4(k+1)^2+1<3\times2^{k+1}\iff 4(k^2+2k+1)+1<3\times 2^k\times 2$$ $$ \iff 2k^2+4k+5/2<3\times2^k$$ From our assumption, we know that $ 4k^2+1<3\times 2^k$, it suffices to just show that for $k\ge6$ that

$$ 2k^2+4k+5/2<4k^2+1 \iff 2k^2-4k-3/2>0 $$

Answer 3

"Assume $4(n+1)^2+1<3∗2^{n+1}$". No. You assume it $4n^2 + 1 < 3*2^n$ and then you PROVE $4(n+1)^2 + 1 < 3*2^{n+1}$.

If we just noodle we get

$4(n+1)^2 + 1 = 4n^2 + 8n + 4 + 1 = (4n^2 + 1) + 8n + 4 < 3*2^n + 8n + 4$.

And that $3*2^{n+1} = 3*2^n*2 = 3*2^n + 3*2^n$. So if we can prove $8n + 4 < 3*2^n$ we are done.

Or alternatively $3*2^{n+1} = 3*2^n + 3*2^n > (4n^2 + 1) + (4n^2 + 1)$. So if we can prove $8n + 4 < 4n^2 + 1$ we are done.

Proving $8n + 4 < 4n^2 + 1$ looks easiest.

$8n + 4 < 4n^2 + 1 \iff 3 < 4n^2 - 8n = 4n(n - 2)$. As $n \ge 6$, $n - 2 \ge 4$ and $4n \ge 24$ and $4n(n-2) \ge 96 > 3$.

....

So that was noodling. To put it all together:

====

1) Base step: Prove if $n =6$ then $4n^2 + 1 < 3*2^n$

Pf: $4n^2 + 1 = 4*6^2 + 1 = 145$ and $3*2^n = 3*2^6 = 192$ and so $4n^2 + 1 = 145 < 192 = 3*2^n$.

2) Induction step: Prove that if $4n^2 + 1 < 3*2^n$ then $4(n+1)^2 + 1 < 3*2^{n+1}$.

Pf: $3*2^{n+1} = 3*2^n*2 = 3*2^n + 3*2^n >$

$(4n^2 + 1) + (4n^2 + 1) = $

$4n^2 + 4n^2 + 2 \ge $

$4n^2 + 4*6n + 2 =$

$4n^2 + 8n + 16n + 2 \ge$

$4n^2 + 8n + 16*6 + 2 =$

$4n^2 + 8n + 4 +94 = $

$4(n^2 + 2n + 1) + 1 + 93=$

$4(n+1)^2 + 1 + 93 > $

$4(n+1)^2 + 1$

3). We have prove that if $4n^2 + 1 < 3*2^n$ the is true for any natural number $n$, then it will be true for the succeeding natural number; $n+1$. And we have proven that $4n^2 + 1 < 3*2^n$ is true for $n = 6$. Therefore we can assumme through successive iterations that it is true for all $n \ge 6$.