$P(n) = 2^n > n^2$, find $k \in \mathbb{N}$ so that $P(k) \Rightarrow P(k+1)$ I've got this problem where I need to find $k \in \mathbb{N}$ so that $P(k) \Rightarrow P(k+1)$ and $P(n) = 2^n \gt n^2$
By induction I have:
$2 = 2^1 > 1^2 = 1$ which is ok with the first condition. Now I'm having troubles with the next step:
If $P(k) \Rightarrow P(k+1)$:
My inductive hypothesis is: $2^k \gt k^2$, and I want to show that $2^{k+1} \gt (k+1)^2$ but I'm stuck on there. What would be the next step, in order to find $k$? 
Any hint will be appreciated. Thanks in advance!
P.S.: Intuitively I see that this is true for $k \geq 5$, but I'm not sure about how to prove it.
 A: I think the point of the question is not to prove by induction, but to find the valid base case $n = k$ such that $P(k) \implies P(k+1)$ for all $n\geq k$. The first value for which $P(k)$ is true AND for which the implication $P(k) \implies P(k+1)$ is true  is the value you give at the very end of what you wrote: $k = 5$. Then you need to prove that it is true for $n = k+1$ for arbitrary $k \geq 5$.
All you need to establish that $k = 5$ is the desired $k$ is show that while $P(1)$ is true, $P(2)$ is false, and so $P(1)\not\implies P(2)$. Also $P(3), P(4) = F$ but $P(5) = T$, and $P(5) \implies P(6)$ is true. (I.e., you will be proving the base case.) THEN, you can prove $P(n)$ is true by induction on $n$, by assuming $P(k)$ is true for some arbitrary $n = k$. And go from there to show this assumption implies $P(k+1)$.
$P(k) = 2^k \gt  k^2 $, for $k\geq 5$ (Inductive hypothesis).
Inductive Step: $$2^{k+1} = 2 \cdot 2^k \overset{P(k)}> 2 \cdot k^2 \overset{?} \geq (k+1)^2 = k^2 + 2k + 1 \iff  k^2 \geq 2k + 1.$$  Is $k^2 \geq 2k + 1$ for $k \geq 5$? 
A: If you expand your inequality, it becomes $2 \cdot 2^k  >  k^2 + 2k + 1 $ .  Your assumed inequality tells you that  $2 \cdot 2^k  >  2 \cdot k^2 $.  Is it the case that $2 \cdot k^2  > k^2 + 2k + 1$ or  $k^2 > 2k + 1$ for $k > 1$ ?
Incidentally, there is a case where the inequality doesn't hold, so the inductive proof will have to be modified slightly...
A: You don't "find $k$". You already have it in your hand, and you assume that the assumption is true for $k$, then you prove that under the assumption that it was true for $k$ it is true for $k+1$.
However as you remark, this is true for $k\geq 5$, but it is not necessarily true for smaller $k$. For example $2^2=2^2$ and $2^3<3^2$, but $2^1>1^2$.
Therefore you cannot prove from $2^k>k^2$ that the same is true for $k+1$, because for $k=1$ this implication is false. What you can do is add to the statement that $k\geq 5$, that is prove the following:

For every natural number $k\geq 5$ it holds that $2^k>k^2$.

Then you can use the fact that $k\geq 5$ in your proof of the induction step.
