$P(n) = 2^n > n^2$, find $k \in \mathbb{N}$ so that $P(k) \Rightarrow P(k+1)$

Question

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.

Answer 1

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.

Answer 2

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...

Answer 3

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$?