I am a CS undergrad and I'm studying for the finals in college and I saw this question in an exercise list:
Prove, using mathematical induction, that $2^n > n^2$ for all integer n greater than $4$
So I started:
Base case: $n = 5$ (the problem states "$n$ greater than $4$", so let's pick the first integer that matches)
$2^5 > 5^2 \implies 32 > 25$ - ok!
Now, Inductive Step:
$2^{n+1} > (n+1)^2$
now expanding
$2 * 2^n > n^2 + 2n + 1$
Well, I can't go on, I don't know how to finish this proof. Could anyone help me with this one?
Also, I know that the statement (inductive hypothesis) is true. Simply, I'll have a number to an exponent $n$ twice, next to $n$ squared and $2n$ (which could be seen as quadratic and linear functions) which "grows" much lower than the exponential one. It could be easily "proved by example" with any $n$ greater than $4$.
I want to know how to prove it algebraically , so my professor does not freak out.
thanks in advance.
$\endgroup$ 02 Answers
$\begingroup$You proved it's true for $n=5$. Now suppose it's true for some integer $n\geq 5$. The aim is to prove it's true for $n+1$. But $$(\spadesuit)\quad2^{n+1}=2\times 2^n>2\times n^2>(n+1)^2.$$ The first inequality follows from the induction hypothesis and as for the second, we know that $(n-1)^2\geq4^2>2$, since $n\geq 5$. We can expand this inequality $(n-1)^2>2$ as follows: \begin{align*} n^2-2n+1>&\,2\\ n^2-2n-1>&\,0\\ 2n^2-2n-1>&\,n^2\\ 2n^2>&\,n^2+2n+1=(n+1)^2, \end{align*} which is the second inequality claimed in $(\spadesuit)$.
$\endgroup$ $\begingroup$do the basis step first and assume true for n
$$ 2^{n+1} = 2^n*2 > 2n^2 = n^2 + n^2 > n^2 + 2n + 1 = (n + 1)^2 $$
$$2^{n+1}>(n + 1)^2$$
now we proved for n+1 case
$\endgroup$
