0
$\begingroup$

Using induction proof, find all the natural numbers $n$ such that $n^2 < 2^n$.

I know that $n$ does not work for $2, 3$, and $4$ but it does work for $0$ and $1$ as well as any number greater than or equal to $5$, I am just not sure how to show this in a proof.

$\endgroup$
  • $\begingroup$ Induction says that your statement holds for all $n$ greater than or equal to some $N$. Can $N$ be less than $5$ based on your observations? $\endgroup$ – Cameron Williams Sep 29 '14 at 0:55
  • $\begingroup$ Yes if it is 0 or 1 but not if it is 2, 3 or 4 $\endgroup$ – Anon123 Sep 29 '14 at 1:00
  • $\begingroup$ If $N=0$ or $1$, what mathematical induction would say is that for all $n\ge N$, your statement ($n^2 < 2^n$) is true. Is this the case? $\endgroup$ – Cameron Williams Sep 29 '14 at 1:07
2
$\begingroup$

Hint

You're on the right track. You can show by exhaustion that $n=0$ and $n=1$ are solutions, but $n\in \{2,3,4\}$ are not.

Next we test our base case $n=5$ and it is a solution.

Suppose for some $n=i$, it is the case that $n^2<2^n$. Hence $i^2<2^i$. We will show that $(i+1)^2<2^{i+1}$, which would complete the proof.

Note:

$$ \begin{align} (i+1)^2 &= i^2+2i+1 \\ (i+1)^2 &<2^i+2i+1 \\ (i+1)^2 &<2^{i+1}-(2^i-2i+1) \end{align} $$

So it remains to show that $2^i\ge2i+1$ so long as $i\ge5$. This can also be proven with induction. Try doing it as an exercise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.