Prove by induction that $4n^2 + 1 < 3\cdot 2^n$ for every $n \ge 6$

Question

My question is about solving for $k+1$

I did the base case and tried to solve the induction step.

this is what I tried

my hypothesis is $4k^2 + 1 < 3\cdot 2^k$ is true then I need to show that it is true for $k+1$

I did right hand side by doing this

$3\cdot2\cdot2^k = 3\cdot 2^{k+1}$ but I am not able to do left hand side please help

Answer 1

HINT: multiplying $$3\cdot 2^n>4n^2+1$$ by $2$ we get $$3\cdot 2^{n+1}>8n^2+2$$ and now show that $$8n^2+2>4n^2+8n+5$$ for $n>2$ so if we have $$3\cdot 2^{n+1}>8n^2+2$$ and $$8n^2+2>4n^2+8n+5$$ then is $$3\cdot 2^{n+2}>4(n+1)^2+1$$

Answer 2

For induction step assume

• $4n^2 + 1 < 3\cdot 2^n$

then

• $4(n+1)^2 + 1 =4n^2+1+8n+4\stackrel{I.H.}< 3\cdot 2^n+8n+4\stackrel{?}<3\cdot2^{n+1}$

$$3\cdot2^n+8n+4<3\cdot2^{n+1}=6\cdot2^{n}\iff 3\cdot2^n>8n+4$$

which is true for $n\ge 4$ (it can be proved by induction again).

Thus we need to verify the base case for $n_0\ge 4$.

Answer 3

$3\cdot2\cdot2^k = 3\cdot 2^{k+1}$

Okay, we have to bring $3*2^k > 4k^2 + 1$ into this.

$3*2*2^k > 2(4k^2 + 1)$

And we want to somehow relate this to $4(k+1)^2 + 1 = 4k^2 + 8k + 5$

So $3\cdot2^{k+1} = 2*3*2^k > 2(4k^2 + 1) = 8k^2 +2 = 4k^2 + 4k^2 + 2$

So we have to show that $4k^2 + 2 \ge 8k + 5$. Which.... seems reasonable.

$k \ge 6$ so $4k^2 > 4*6*k$ and:

$3\cdot2^{k+1} = 2*3*2^k > 2(4k^2 + 1) = 8k^2 +2 = 4k^2 + 4k^2 + 2\ge 4k^2 + 24k + 2 = 4k^2 + 8k + 16k + 2$.

So now we just need to show $16k + 2 > 5$. That's..... well, that's.....

Again $k \ge 6$ so $16k \ge 16*6$.

$3\cdot2^{k+1} = 2*3*2^k > 2(4k^2 + 1) = 8k^2 +2 = 4k^2 + 4k^2 + 2\ge 4k^2 + 24k + 2 = 4k^2 + 8k + 16k + 2\ge 4k^2 + 8k + (16*6 + 2) > 4k^2 + 8k +4 + 1 = 4(k+1)^2 + 1$.

And that's the induction step.