1
$\begingroup$

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.

  • 0
    just changed it. thanks2012-09-16

5 Answers 5

0

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.

  • 0
    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!2012-09-16
2

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.

  • 0
    ok this looks like a real deductive/direct proof. upvoted2012-09-16
2

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.

1

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.

  • 0
    A downvote without an explanatory comment is less than helpful $-$ especially when it’s on an answer that is in fact correct.2012-09-17
0

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

  • 0
    @Wuschelbeu$t$el: Thank you; I’ve made an answer ou$t$ of it.2012-09-16