Identify the error in the following condensed proof 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.
 A: 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$.
A: 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$.
