2
$\begingroup$

Identify the error in the following condensed proof of the statement, “If $n$ is a positive integer for which $n^2 < 2^n$, then $(n + 1)^2 < 2^{n + 1}$.” Then modify the hypothesis so that the resulting statement and proof are true.

Proof. Now $(n+1)^2 = n^2 + 2n + 1$ and, because $n^2 < 2^n$, it follows that $n^2 + 2n + 1 < 2^n + 2n + 1$. Finally, $2n + 1 < 2^n$ and so $(n + 1)^2 = n^2 + 2n + 1 < 2^n + 2^n = 2^{n + 1}$.

The textbook solutions state that the incorrect statement is $2n + 1 < 2^n$. It justifies this by appeal to the counterexample of $n = 1$, where $2(1) + 1 \not < 2^1$.

However, before stating that $2n + 1 < 2^n$, the proof explicitly states that $n^2 < 2^n$. In other words, the proof assumes that the hypothesis ($n^2 < 2^n$) is true. Therefore, the statement $2n + 1 < 2^n$ must be valid because $n \ge 5$.

I would greatly appreciate it if anyone could take the time to review this reasoning.

Is my reasoning correct or is the textbook solution correct? If my reasoning is incorrect, please explain why.

Thank you.

$\endgroup$
  • $\begingroup$ @mfl: That makes the claim fail for $n=1$, not for $n=2$. $\endgroup$ – hmakholm left over Monica Dec 17 '16 at 14:20
3
$\begingroup$

The proof assumes only $n^2 < 2^n$. $n=1$ satisfies that hypothesis since $1^2 < 2^1$, so if you want to prove this statement, you have to prove it for $n=1$ and you can't use any reasoning that doesn't apply to $n=1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But it says "If $n$ is a positive integer for which $n^2 < 2^n$." Therefore, $n \not = 1$. What am I misunderstanding? $\endgroup$ – The Pointer Dec 17 '16 at 14:19
  • 2
    $\begingroup$ @ThePointer The inequality $n^2 < 2^n$ is true for $n=1$ and $n \geq 5$. If you plug in $n=1$ into the inequality $n^2 < 2^n$, you will clearly see that it satisfies the statement. $\endgroup$ – Noble Mushtak Dec 17 '16 at 14:20
  • $\begingroup$ Doesn't the $<$ symbol represent strictly less than? Wouldn't $\le$ represent less than or equal to? $\endgroup$ – The Pointer Dec 17 '16 at 14:21
  • 1
    $\begingroup$ @ThePointer Yes, that is correct. For $n=1$, $n^2$ is strictly less than $2^n$. $$1 < 2 \implies 1^2 < 2^1$$ $\endgroup$ – Noble Mushtak Dec 17 '16 at 14:22
  • $\begingroup$ I've been reading it incorrectly and confusing myself! Thank you for your assistance. $\endgroup$ – The Pointer Dec 17 '16 at 14:23
2
$\begingroup$

Requirements

In the recurrence proof, you define some $P(n)$ property and then two things are required :

  • an initial $n_0$ such that $P(n_0)$ is verified
  • showing that assuming $n\ge n_0$ then $P(n)\Rightarrow P(n+1)$

Second requirement violated

If we define $P(n)="n^2<2^n"$ then we can verify that $P(0)$ and $P(1)$ are true but that $P(2)$ is false.

So it means that somewhere in the proof something is used which is not true assuming only $n\ge1$ (according to our second requirement with $n_0=1$).

And as you noticed this is the fact $2n+1<2^n$ which in this case for $n=n_0=1$ turns out to be $2\times1+1<2^1$ or $3<2$ which is false.

Trying to repair

So to repair the proof you have either to change your hypothesis to $Q(n)="n^2<2^n\space and\space 2n+1<2^n"$ and work your way from there or try to see if you could proove this second hypothesis on $2n+1$ in a simple way.

It turns out you can : $(n+1)^2 = n^2+2n+1 $

  • $n^2<2^n$ according to hypothesis $P(n)$

  • $n<\frac{2^n}{n}$ is equivalent (for all $n>0$)

  • so we have $(n+1)^2<2^n + 2^n.\frac{2}{n}+1$ which could be rewritten $2^{n+1}-2^n(1-\frac{2}{n}-\frac{1}{2^n})$

It is trivial to show that $f(n)=1-\frac{2}{n}-\frac{1}{2^n}$ is an increasing function.

$f(1)=-\frac{3}{2}<0$ not good

$f(2)=-\frac{1}{4}<0$ not good either

$f(3)=\frac{5}{24}>0$ this is nice, so since $f(n)$ is increassing, we know this is true for all $n\ge3$.

This results in $(n+1)^2<2^{n+1}-a(n)$ where $a(n)>0$ so we can conclude $(n+1)^2<2^{n+1}$.

Back to verifying $P(n_0)$

We were able to proove that for $n\ge3$ then $P(n)\Rightarrow P(n+1)$. [note that we needed $n>0$ at some point, but that is covered by $n\ge3$]

But now, our first requirement in the recurrence proof fails again, because $P(3)$ is false. So we try $P(4)$, false too and then $P(5)$ which is true.

So finally we have an $n_0=5$ which verify both proof requirements. We can then assert that $\forall n\ge n_0$ we have $n^2<2^n$.

| cite | improve this answer | |
$\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.