Help on Inequality Proof I'm trying to solve a proof for this inequality. I already have the solution, but have a question about the solution. Here's what I have so far:
Prove  $2^n > n^2$ for  $n > 4$
Base Case $n=5$. $32 > 25$. True.
Inductive Case: Assume $2^n > n^2$ is true for $4 < n \leq k$. In particular, for $2^k > k^2$. Prove $2^{k+1} > (k+1)^2$.
$$2^{k+1} = 2 \cdot 2^k > k^2 + 2k + 1$$.
Here's where I get stuck. The solution says that $2 \cdot 2^k > 2 \cdot k^2$. Ok, makes sense. Then it says that that is equal to $k^2 + k^2 > k^2 + 2k + 1$.
Where did $k^2 + k^2$ come from?
 A: Previously posted answers have amply dealt with the question, but I think it is worth making some methodological remarks.  
The approach that is being taken to the question "When is $2^n >n^2$?" is essentially subtractive.  There is a better approach, that deals well with a range of similar problems.  For this particular problem, it will seem more complicated, because division feels more complicated than subtraction.  
Let $f(n)=n^2/2^n$.  We want to show that $f(n)<1$ when $n >4$.  Note that 
$$f(n+1)=\frac{(n+1)^2}{2^{n+1}}=\frac{n^2}{2^n}\frac{(n+1)^2}{n^2}\frac{1}{2}$$ 
Thus 
$$f(n+1)=f(n)\left(1+1/n\right)^2/2$$
But $(1+1/n)^2/2<1$ for any $n \ge 3$.  Thus from $n=3$ on, $f(n)$ is decreasing.  Since $f(4)=1$, we conclude that $f(n)<1$ for all $n \ge 5$.
Similarly, let us show that from some identified point on, $3^n >n^4$.  Let $f(n)=n^4/3^n$.  A calculation similar to the one above shows that
$$f(n+1)=f(n)(1+1/n)^4/3$$
The term that $f(n)$ is multiplied by is less than $1$ when $n \ge 4$, so from $n=4$ on, $f(n)$ is decreasing.   A little experimentation shows that $f(7)>1$ and $f(8)<1$.  So $f(n)<1$ from $n=8$ on.  
Note for purists: The word "induction" has not been mentioned. However, like in most problems about positive integers, induction is being used.  In the  $2^n > n^2$ problem,  from the facts that $f(n+1)<f(n)$ for $n \ge 3$ and that $f(4)=1$, we are quietly concluding that $f(n)<1$ for all $n>4$. In principle this step requires mathematical induction.  In practice we regard this step as obvious, and do not use the "i" word.
A: $2k^2 = k^2 + k^2$, so:
$$k^2 + 2k + 1 < k^2 + k^2 = 2k^2 < 2 \cdot 2^k$$ 
It's easy to see that $2k^2 < 2 \cdot 2^k$ from the induction hypothesis, so you only need to prove $k^2 + 2k + 1 < k^2 + k^2$.
