0
$\begingroup$

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?

| cite | improve this question | | | | |
$\endgroup$
  • 2
    $\begingroup$ Then you can start your induction from $3$. $\endgroup$ – QZ0 Sep 9 '16 at 0:00
  • $\begingroup$ @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? $\endgroup$ – idknuttin Sep 9 '16 at 0:03
  • 1
    $\begingroup$ You can have finite number of base cases. For your second question, you should understand the difference between "sufficient condition" and "necessary condition". $\endgroup$ – QZ0 Sep 9 '16 at 0:07
1
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ why can we just say that the final part, $a^2 \gt 2a+1$ is obvious and does not require a proof? $\endgroup$ – idknuttin Sep 9 '16 at 0:16
  • 1
    $\begingroup$ 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? $\endgroup$ – David Bowman Sep 9 '16 at 0:38
  • $\begingroup$ 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? $\endgroup$ – idknuttin Sep 9 '16 at 0:46
  • 1
    $\begingroup$ 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}$. $\endgroup$ – David Bowman Sep 9 '16 at 0:52
2
$\begingroup$

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.

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

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.