Prove by induction that $4n^2 + 1 < 3\cdot 2^n$ for every $n \ge 6$ 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
 A: 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$$
A: 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$.
A: $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.
