<s>[INST] 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
 [/INST] $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.
</s>