Proving $2^n > (n+1)^2$ for $n\geq 6$ by induction.

Question

So here is what I have to prove by induction:

$2^n\gt(n+1)^2$ for $n\ge6$

So, first lets say $n=6$

$$2^6\gt(6+1)^2$$ $$64\ge49$$ Now, assume $n=k$ $$2^k\gt(k+1)^2\text{ for } k\ge6$$

Prove $n=k+1$ is true $$2^{k+1}>(k+2)^2$$ $$2^k *2> k^2+4x+4$$ We can replace $2^k$ with $(k+1)^2$ $$(k+1)^2*2>k^2+4x+4$$ $$k^2+2>4$$ $$k^2>2$$ Now, since $k\ge6$, $k^2$ must be greater than $2$ $$$$ So, my question is, did I do the proof correctly, or is there a more rigorous method to get this done?

Answer 1

If I were you, this is how I would structure the meat of your proof: \begin{align} 2^{k+1} &= 2^k\cdot 2\tag{definition}\\[0.5em] &> 2\cdot(k+1)^2\tag{inductive hypothesis}\\[0.5em] &= 2(k^2+2k+1)\tag{expand}\\[0.5em] &= 2k^2+4k+2\tag{expand again}\\[0.5em] &> k^2+4k+4\tag{since $k\geq 6$}\\[0.5em] &= (k+2)^2.\tag{factor} \end{align} That is really all you need to show (of course, in your formal write up, you should include the base case, the inductive assumption, etc.).

Answer 2

Hint: $2 \geq ((n+1)/n)^2$ for your assumption $n \geq 6$.