Proof that $n^2 < 2^n$

Question

How do I prove the following statement by induction?

$$n^2 < 2^n$$

P(n) is the statement $n^2 < 2^n$

Claim: For all n > k, where k is any integer, P(n)

(since k is any integer, I assume I have to prove this for positive and negative integers)

So let base case be P(1), and I have to prove P(n) for n >= 1 and n < 1

P(1) is $1^2 < 2^1$ which is clearly true.

Induction hypothesis: $k^2 < 2^k$

Inductive step $(k+1)^2 < 2^{(k+1)}$

$(k+1)^2 = k^2 + 2k + 1$

$k^2 + 2k + 1 < 2^k + 2k + 1$ by inductive hypothesis

Not sure how to proceed. Is my previous intuition that I have to prove this for n >= 1 and n < 1 correct?

Answer 1

$$n^2<2^n\Longleftrightarrow 2\log n<n\log 2\Longleftrightarrow\frac{\log n}{n}<\frac{\log 2}{2}$$

But we know that $\,\displaystyle{\frac{\log n}{n}\xrightarrow[n\to\infty]{}0}\,$ , so the above inequality's definitely true from one definite index $\,n\,$ and on...but not for all the naturals!

Answer 2

Your statement is only true for $n=0$, $n=1$ and $n \geq 5$.
Than start with $n=5$, this gives $5^2=25 < 2^5 = 32$

So Assume it is true for $n$. Than we know that $$2^{k+1}= 2 \cdot 2^k > 2 k^2>k^2+2k+1=(k+1)^2$$ (as $n^2>2n+1$ for all $n\geq 3$ and as we started with $n=5$ this is always true)

Answer 3

If you want to use induction, I assume you have checked the base case $n = 5$. To do the inductive step, assume that the statement holds for some $k$: $k^2 < 2^k$, and then under this assumption, you want to check that the statement holds for $k+1$: $(k+1)^2 < 2^{k+1}$. Well,

$$ (k+1)^2 = k^2 + 2k + 1 < 2^k + 2k + 1 $$

by the inductive hypothesis. When is $2^k + k + 1 < 2^{k+1}$. Well,

$$\begin{align} 2^k + k + 1 < 2^{k+1} &\iff k+1 < 2^{k+1} - 2^k \\ &\iff k+1 < 2^k. \end{align}$$

It is sufficient to show that $k+1 < 2^k$ for all $k \geq 5$. One way to do this is by induction. You can easily show the base case $5 + 1 < 2^5$. Now, assume that it holds for some $j \geq 5$, and we want to show that it also holds for $j+1$. Thus, we want to show that if $j+1 < 2^j$, then $(j+1) + 1 < 2^{j+1}$. This follows almost immediately since

$$ (j+1) + 1 < 2^j + 1 < 2^j + 2^j = 2^{j+1} $$ You should note that the inequality $1 < 2^j$ is not true in general, but it is true for $j > 1$ (and in particular for $j \geq 5$). Thus, we have shown that $k+1 < 2^k$ for all $k \geq 5$, and this was precisely what we needed for the inductive step of the original proof.

It should be noted that induction is indeed not the easiest way to prove this inequality, but if we want to strictly use induction, then something like this proof (and the consequent proof of the statement $k+1 < 2^{k}$ for $k \geq 5$) is the way to go.

As a final note, to show what I mean about the easiest proof, as it was noted above, we have $n^2 < 2^n$ if and only if $\frac{\log n}{n} < \frac{\log 2}{2}$. Now, $f(x) = \frac{\log(x)}{x} \implies f'(x) = \frac{1 - \log x}{x^2} < 0$ when $x > e$. Thus, the function is strictly decreasing for $x > e$. Coupled with the fact that $f(x) \to 0$ as $x \to \infty$, it then suffices to find the first integer $t$ such that $\frac{\log t}{t} < \frac{\log 2}{2}$. This happens to be $t = 5$.

Added: Thomas' hint is a bit nicer than my own answer, as it requires only check the values for which $n^2 > 2n +1$ which can be done with basic algebra.

Answer 4

Hint only: For $n \geq 3$ you have $n^2 > 2n + 1$ (this should not be hard to see) so if $n^2 < 2^n$ then consider $$ 2^{n+1} = 2\cdot2^n > 2n^2 > n^2 + 2n+1 = (n+1)^2. $$ Now this means that the induction step "works" when ever $n\geq 3$. However to start the induction you need something greater than three. By trial an error you can find the smallest $n(\geq0)$ such that $n^2 < 2^n$.

Answer 5

As a fun fact another way to see that this inequality is true eventually is to compare the sum of the numbers in the $n-1$ 'st row of pascal's triangle to the $n$'th triangular number, which appears in the $n+1$ 'st row and occurs along one of the diagonal's of pascal's triangle. See the link for more details, http://mathforum.org/workshops/usi/pascal/pascal_triangular.html. The fact presented on that page plus the fact the sum of the row of pascal's triangle is a power of two can be used to prove the desired inequality.

This amounts to proving that $\frac{n(n+1)}2 \lt 2^\left(n-1\right)$ which is stronger than the original inequality, since $n^2 \lt n(n+1)$ for $n \gt 0$ .