Please help me prove $n^2 ≤ 2^{n+1}$ by the well-ordering (not induction) $n\in\Bbb N \setminus \{{0\}}$
I've assumed that $n=1$ is not counter example so $m > 1$ and now try with $n = m-1$.
$$(m-1)^2 ≤ 2^{m-1+1} = 2^m$$
I'm stuck here.
Asked
Active
Viewed 68 times
0
-
Proving by well ordering and induction is essentially the same, though... – Rushabh Mehta Dec 19 '21 at 15:35
-
Let $n$ be the smallest natural for which $n^2\geq2^{n+1}$. If $n=0$, this is false, so $n-1$ is a natural, and thus $(n-1)^2<2^n$. Since $n\leq2^{n-1}$ for $n>0$ (prove by induction), $2n-1<2^n$, so $n^2<2^{n+1}$, a contradiction. – Rushabh Mehta Dec 19 '21 at 15:42
-
For large n, the derivative of n^2 is much less than n while the derivative of 2^(n+1) is about the same as 2^(n+1) . Eventually, 2^(n+1) must be higher than n^2. – Wakem Dec 20 '21 at 21:07
-
As Don Thousand said, proof by well-ordering and by induction are pretty much the same thing. Work out the proof by induction. Then convert it to a proof by well-ordering: Let $A$ be the set of all $n$ for which the statement is false. Assume $A \ne \emptyset$ and let $k$ be the smallest element of $A$. Then either $k = 1$, which cannot be since $n=1$ works (check it, don't "assume" it). Or else the statement is true for $n = k-1$. Prove what would be the "induction step" in an induction proof to show this means the statement is true for $n=k$ as well, contradicting that $k \in A$. – Paul Sinclair Dec 20 '21 at 21:47