Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I saw a video of somebody saying that you can prove this by saying that $x+1$ will grow by $2$ on the LHS and by $(x+1)^{2}/x^{2}$ on the RHS. But I am not convinced that this is a clean deductive proof. Do you agree and if so, how can one make a clean argument? I was thinking about taking the derivative twice and then showing that the ratio blows up, but this way I only show that it's valid as I go to infinity, and not for the finite values.

EDIT: Perhaps I can perform long division and show it that way.

EDIT2: I have already solved this with induction. My intention is to "challenge" the deductive proof that I saw in the video.

share|improve this question
    
There is no $n$ in $2^x \geq x^2$. –  William Sep 16 '12 at 23:21
    
just changed it. thanks –  Wuschelbeutel Kartoffelhuhn Sep 16 '12 at 23:22

5 Answers 5

up vote 1 down vote accepted

Mathematical induction is a form of deductive proof. (It’s unfortunate that its name makes it sound like induction in the sense that is opposed to deduction $-$ coming to a conclusion on the basis of a large number of positive examples and no counterexamples.) The argument sketched in the video is essentially the induction step of a proof by induction; it does not pretend to be anything else. It’s informal but correct.

share|improve this answer
    
Once I expand (x+1)^2/x^2 and break up the fraction and cancel common factors: I get for the rate of growth: 2>1+2/x+1/x^2...which is true for integers AND reals above 4. –  Wuschelbeutel Kartoffelhuhn Sep 16 '12 at 23:48
    
A downvote without an explanatory comment is less than helpful $-$ especially when it’s on an answer that is in fact correct. –  Brian M. Scott Sep 17 '12 at 20:52

Take the function $f(x)=2^x-x^2$, we have that $f'(x)=\textrm{ln}(2)\cdot 2^x-2x\geq 0$ for all $x\geq 4$. Also, noting that $f(4)\geq 0$, we can see that $f(x)\geq 0$ for all $x\geq 4$, and the result follows.

share|improve this answer
    
Maybe the only problem now is too proof that $\textrm{ln}(2)\cdot 2^x\geq 2x$ for all $x\geq 4$, but this is much more easier. –  Integral Sep 16 '12 at 23:53
    
ok this looks like a real deductive/direct proof. upvoted –  Wuschelbeutel Kartoffelhuhn Sep 16 '12 at 23:55

This sort of argument is a special case of inequalities proved by multiplicative telescopy - which represents the function $\rm\:f(n)\:$ as a product of its term ratios $\rm\: f(k+1)/f(k),\:$ namely

$$\rm f(0)\ \prod_{k\:=\:0}^{n-1}\, \frac{f(k+1)}{f(k)}\ = \ \ \color{#C00}{\rlap{--}f(0)}\frac{\color{green}{\rlap{--}f(1)}}{\color{#C00}{\rlap{--}f(0)}}\frac{\color{royalblue}{\rlap{--}f(2)}}{\color{green}{\rlap{--}f(1)}}\frac{\phantom{\rlap{--}f(3)}}{\color{royalblue}{\rlap{--}f(2)}}\, \cdots\, \frac{\color{brown}{\rlap{--}f(n-1)}}{\phantom{\rlap{--}f(n-2)}}\frac{f(n)}{\color{brown}{\rlap{----}f(n-1)}}\ =\ \ f(n) $$

Therefore if $\rm\:f(0)>g(0)\:$ and if also $\rm\:\dfrac{f(k+1)}{f(k)} > \dfrac{g(k+1)}{g(k)}\:$ then the product of these telescope to

$$\rm f(n)\, =\, f(0)\ \prod_{k\:=\:0}^{n-1}\, \frac{f(k+1)}{f(k)}\ >\ g(0)\ \prod_{k\:=\:0}^{n-1}\, \frac{g(k+1)}{g(k)}\, =\, g(n) $$

See here for a sketch of a telescopic proof of the more general result that exponentials grow faster than polynomials. As I have emphasized here before in many posts, by means of cancelling complicated expressions, telescopy often reduces induction problems to trivialities (here if we work with $\rm\,f/g,\,$ the proof reduces to the trivial proof that a product of terms eventually $> 1$ is itself eventually $> 1$). Difficult problems involving hyperrational functions (i.e. $\rm\ f(n+1)/f(n) = $ rational function of $\rm\:n,\:$ e.g. powers, exponentials, factorials) are, after application of telescopy, greatly simplified to trivial problems about rational functions - functions so simple that questions about such can be decided mechanically by algorithms.

share|improve this answer

You can do this by induction. To start out with, $2^4\ge 4^2$. Next, assume that, for $n\ge 4$, $2^n\ge n^2$. Then $$2^{n+1}=2\cdot 2^n\ge 2n^2\ge \frac{(n+1)^2}{n^2}n^2=(n+1)^2$$ because $(n+1)^2/n^2=(1+1/n)^2\le\frac{25}{16}<2$ for $n\ge 4$.

share|improve this answer
    
the restriction is to avoid induction. i'm only asking w.r.t. to decuctive/direct proof. i have already done the same exercise with induction before, but thx anyway. –  Wuschelbeutel Kartoffelhuhn Sep 16 '12 at 23:24
    
there is no mention of induction in the question –  Jonathan Sep 16 '12 at 23:25
    
sorry, i should have made it clearer that im only talking about deductive proofs –  Wuschelbeutel Kartoffelhuhn Sep 16 '12 at 23:28
    
@Wuschelbeutel: Mathematical induction is a form of deductive proof. And the argument sketched in the video is essentially the induction step of a proof by induction; it does not pretend to be anything else. It’s informal but correct. –  Brian M. Scott Sep 16 '12 at 23:35
    
@BrianM.Scott: Ok I just did the expansion and division and it makes sense now. –  Wuschelbeutel Kartoffelhuhn Sep 16 '12 at 23:39

This proof is not good for the case that $x$ is not a natural number. You can not deduce from the proof that, for example, $2^{1.5} \geq 1.5^2$

Added: the proof you gave also resort to induction IMO since if I ask you why $2^{10} \geq 10^2$ you will tell me about the inequality for $x=9$ - but when I ask you about the inequality for $x=9$ you will have to tell me about the inequality for $x=8$ and so forth untill you reach the base case.

share|improve this answer
    
I claim it's not even good enough for the naturals. But I agree with you on the reals in that case. I assume, one would simply add the fractional part explicitly as a symbol. –  Wuschelbeutel Kartoffelhuhn Sep 16 '12 at 23:30
    
@WuschelbeutelKartoffelhuhn - I added some information –  Belgi Sep 16 '12 at 23:38
    
Yes, that's the remark that was also made by Brian M. Scott. However, I fail to see how this proof (from the video) doesn't qualify for reals also. You end up with the expression 1>2/x+1/x^2 (rate of growth comparison between LHS and RHS), which is true for x larger than 4...even non-integers! –  Wuschelbeutel Kartoffelhuhn Sep 16 '12 at 23:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.