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

Solution 1:

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.

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

Solution 3:

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.