# Prove that $2^{n+1} \gt n^2$ for every positive integer $n$.

Prove that $2^{n+1} \gt n^2$ for every positive integer $n$.

I have to prove this using mathematical induction, I know how to start the proof but I get stuck towards the end because I think I either did something wrong or do not know how to continue it.

Here are all of the steps I have done so far:
First I prove that $1 \in S$
This is obviously true because $2^{1+1} \gt 1^2$
Now assume that $a \in S$, we have $2^{a+1} \gt a^2$, now I have to prove that $a+1 \in S$, i.e. $2^{a+2} \gt (a+1)^2$.

$2^{a+2}$ becomes $2 \times 2^{a+1}$ and $(a+1)^2$ becomes $a^2+2a+1$.

We now have $2 \times 2^{a+1} \gt a^2+2a+1$

Multiply both sides of $2^{a+1} \gt a^2$ by 2 and obtain $2 \times 2^{a+1} \gt 2a^2$

to complete the proof all I have to prove is that $2a^2 \gt a^2 +2a +1$

subtracting $a^2$ from both sides I get $a^2 \gt 2a+1$, but this is only true for $a \ge 3$ and I need to prove if for all positive integers.

What did I do wrong, should I have taken a different approach or is there a way to finish what I started?

• Then you can start your induction from $3$. – QZ0 Sep 9 '16 at 0:00
• @ThomasAndrews so I can have two base cases, when $a=1$ and when $a=2$, then prove for $a+1$, can I have two base cases? But how can $a=1$ and $a=2$ work for $2^{a+1} \gt a^2$, but not work for $a^2 \gt 2a+1$ if this is derived from the first inequality? – idknuttin Sep 9 '16 at 0:03
• You can have finite number of base cases. For your second question, you should understand the difference between "sufficient condition" and "necessary condition". – QZ0 Sep 9 '16 at 0:07

You need to prove more base cases.

In the case of $a=1$, we have $2^{1+1} = 4 \gt 1^2 = 1$. In the case of $a=2$, we have $2^{2+1} = 8 \gt 2^2 = 4$.

Assume that for some $a \in \mathbb N, a\ge 3,$ that $2^{a+1} \gt a^2$. Then we must show that the $a+1$ case is true. We have $2^{(a+1)+1)} = 2^{a+1} * 2^1 > 2 * a^2$, since by assumption $2^{a+1} \gt a^2$. Then we have $2^{a+1} * 2^1 > 2 * a^2 > (a+1)^2 = a^2 + 2a + 1$ for $a \ge 3$, and we are done.

• why can we just say that the final part, $a^2 \gt 2a+1$ is obvious and does not require a proof? – idknuttin Sep 9 '16 at 0:16
• Well, you stated in your question that it's only true for $a \ge 3$, so I assumed it was given or perhaps proven earlier. There are many ways of proving this though. Any ideas? – David Bowman Sep 9 '16 at 0:38
• I could probably use mathematical induction again but I don't think that would be necessary, we could move everything to one side and complete the square to get $(a-1)^2 -2 \gt 0$ can we say this is obvious for $a \ge 3$, or is there an easy way of proving it? – idknuttin Sep 9 '16 at 0:46
• You might use the quadratic formula to discover that $f(a) = a^2 - 2a -1$ has zeroes $1- \sqrt{2}$ and $1+ \sqrt{2}$, both of which are less than $3$. Since f is increasing for $a \gt 1, f(a) \gt 0$ for $a \gt 1 +\sqrt{2}$. – David Bowman Sep 9 '16 at 0:52

Another way is using the function $$f(x)=2^{x+1}-x^2$$ whose derivative is $$f'(x)=2^{x+1}\ln 2-2x$$ One has $$2^{x+1}\ln 2-2x\gt 0\iff2^x\ln 2\gt x$$ Hence the derivative is always positive and (besides of increasing) so is the function $f(x)$ for $x\gt 0$ since $f(0)=2$. In particular for $x$ integer positive this is true.

• But then, how do you prove that $2^x\ln(2)>x$? – gniourf_gniourf Dec 4 '16 at 17:16