13
$\begingroup$

How do I prove the following statement by induction?

$$n^2 \lt 2^n$$

$P(n)$ is the statement $n^2 \lt 2^n$

Claim: For all $n \gt 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 \ge 1$ and $n \lt 1$

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

Induction hypothesis: $k^2 \lt 2^k$

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

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

$k^2 + 2k + 1 \lt 2^k + 2k + 1$ by inductive hypothesis

Not sure how to proceed. Is my previous intuition that I have to prove this for $n \ge 1$ and $n \lt 1$ correct?

$\endgroup$
  • 11
    $\begingroup$ One problem is that the claim is not true. $2^2 \not < 2^2$ $\endgroup$ – Chris Eagle Mar 3 '13 at 22:46
  • 4
    $\begingroup$ Also, $3^2\not<2^3$, and $4^2\not<2^4$ but it holds for $n\ge 5$. $\endgroup$ – Berci Mar 3 '13 at 22:55
  • 10
    $\begingroup$ This question has been asked here several times before. I always like to point out a nice combinatorial proof, for $n\ge 5$: $n^2=\binom{n}{1}+\binom{n}{2}+\binom{n}{n-2}<\sum_k\binom{n}{k}=2^n$. $\endgroup$ – Andrés E. Caicedo Mar 4 '13 at 0:43
  • 2
    $\begingroup$ Related. $\endgroup$ – Andrés E. Caicedo Jul 9 '13 at 4:38
9
$\begingroup$

$$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!

$\endgroup$
  • 3
    $\begingroup$ Here you use a lot of math which isn't allowed when you have to prove such inequalities in classes. In my class we defined the logarithm several weeks after Induction. And you need the monoticity of the logarithm. And btw the Question is tagged with induction $\endgroup$ – Dominic Michaelis Mar 3 '13 at 23:04
  • 2
    $\begingroup$ Here we define the exponential and logarithm roughly about the same time as induction in the 11th high school grade, and monotonicity of logarithm is trivial since its derivative is always positive...and this also is high school stuff. $\endgroup$ – DonAntonio Mar 3 '13 at 23:06
  • 1
    $\begingroup$ i mean in university not in high school $\endgroup$ – Dominic Michaelis Mar 4 '13 at 10:23
  • $\begingroup$ (+1) can you explain what do you mean by 'not' for all naturals ? $\endgroup$ – NewBornMATH Mar 24 at 19:54
  • $\begingroup$ @NewBornMATH The inequality is false for $\;n=1,2,3,4\;$ , but true for any natural $\;n\ge5\;$ . This is easily proved with induction, for example. $\endgroup$ – DonAntonio Mar 24 at 22:09
13
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thomas: Your method of working backwards sure trumps mine as you have reduced the proof to showing the inequality $n^2 > 2n +1$, which any algebra student should be able to do. $\endgroup$ – JavaMan Mar 3 '13 at 23:39
  • 2
    $\begingroup$ This proof is very simple and uses induction properly. This answer should be on top. $\endgroup$ – user137035 Feb 7 '15 at 15:50
  • 2
    $\begingroup$ How do you know $ 2n^2 > n^2 +2n + 1 $ is true? $\endgroup$ – user223868 Jun 15 '16 at 7:29
  • $\begingroup$ @Ibrahim: I will leave that as an exercise for you :) You can always ask this as a new question if you need some help. $\endgroup$ – Thomas Jun 15 '16 at 12:55
  • $\begingroup$ Why the downvote? Help me out so that I can improve the answer ... $\endgroup$ – Thomas Dec 4 '17 at 21:44
9
$\begingroup$

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.

This idea of breaking a problem down into subsequent steps (if we need to show this, it suffices to show that, etc) is very much like how mathematicians solve problems.

It should be noted that induction is probably not the easiest way to derive 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 one way to go.

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 much 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.

$\endgroup$
  • $\begingroup$ How do you find that 't' without using log table $\endgroup$ – NewBornMATH Mar 24 at 20:06
  • 1
    $\begingroup$ I happen to know that $\ln 2 = 0.693...$, while $\ln 3 = 1.097...$, and $\ln(5) = 1.609$. You could also use a calculator of course :-) $\endgroup$ – JavaMan Mar 24 at 21:08
  • $\begingroup$ (+1) for quick reply : ) $\endgroup$ – NewBornMATH Mar 24 at 21:12
5
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ Why is $2k^2 > k^2+2k+1$? $\endgroup$ – Al Jebr Dec 3 '17 at 20:20
4
$\begingroup$

Assuming that $n\geq 5$, and $k^2<2^k$, $$2^{k+1}=2\cdot2^k>2k^2=k^2+k^2=k^2+2k+k(k-2)$$ Since the starting integer is $5$ so $k(k-2)$ is at least $15>1$ and therefore $$2^{k+1}>k^2+2k+1=(k+1)^2.$$

$\endgroup$
  • $\begingroup$ This is probably the simplest way to do this by induction. $\endgroup$ – matrixx May 18 '18 at 15:50
-2
$\begingroup$

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$ .

$\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.