# Is this a valid deductive proof of $2^x \geq x^2$ for all $x \geq 4$?

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.

-
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

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.

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

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

-

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

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

-
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