3

This is what I came up with so far:

Inductive step: assume $2^n > n^4$. Need to prove $2^{n+1} > (n+1)^4$ $$ 2^{n+1} = 2 \cdot 2^n > 2 \cdot n^4\\ (2 \cdot n^4)^{1/4} = (2)^{1/4} \cdot n > n+1 \implies 2n^4 > (n+1)^4 \implies 2^n > (n+1)^4 $$

Is there a better way to solve this problem?

Yuriy S
  • 31,474
JJTO
  • 141
  • 3
    Looks like a good start. You ignore the base cases though...after all $2^3$ is not greater than $3^4$. – lulu Aug 15 '16 at 20:09
  • 1
    You need to add the conditions for which this is true (in this case, $n \ge 5$), and check for the first value. Assume this has already been done. Then, the inequality $2^{1/4}n > n+1$ is not obvious, it requires justification. Otherwise this is probably as good as it gets. –  Aug 15 '16 at 20:10
  • @mathguy, note, $2^{1/4}\cdot5=5.946\lt5+1$, so this induction doesn't actually work unless you start at $n=6$. – Barry Cipra Aug 15 '16 at 20:20
  • $2^6$ is not greater than $6^4$ ! – lulu Aug 15 '16 at 20:29
  • note that $2^{16}=16^4$. After that your argument works...but the least base case for which the claim is true is $n=17$. – lulu Aug 15 '16 at 20:30
  • lol, sorry all for not paying attention... the "$\ge 5$" in my comment stinks. –  Aug 15 '16 at 20:41
  • @lulu, you are quite right. I was being inattentive too. (More precisely, I was only being attentive to the inequality $2^{1/4}n\gt n+1$.) – Barry Cipra Aug 15 '16 at 20:57
  • @BarryCipra I knew the inequality was true due to the basic exponentials > powers fact, but I think this is a problem that goes to show why it is important to specify what your base case is. I did not even know what your comment was referring to until I verified OP's argument, which relies on $n\geq6$ but more subtly on $n\geq17$. – Daniel W. Farlow Aug 15 '16 at 21:00
  • @DanielW.Farlow, I can't speak for mathguy, but as for myself, I accepted $n=5$ as the appropriate base case after doing a quick mental verification that $2^5\gt5^2$ instead of a correct comparison with $5^4$. In short, it was, for me at least, a silent, deadly brain fart. – Barry Cipra Aug 15 '16 at 21:23

4 Answers4

2

As others have noted, your induction proof ultimately suffers from establishing what your base case is. Your deduction that $$ 2^{1/4}(n)>n+1 $$ requires $n\geq6$, as Barry notes, but your inequality is not even true until $n\geq17$, as lulu notes. This means that your base case should be, at minimum, for when $n=17$. Then you can proceed exactly as you have done.

"Is there a better way to solve this problem?" Sure: use the fact that any exponential function eventually overtakes any power function (with bases $>1$ of course). But that is not all that insightful here--perhaps you are after something more intuitive perhaps? If so, please specify.

Daniel W. Farlow
  • 22,531
1

There is another inductive way, I don't know if better or worse:

Our goal is to prove that $2^{n+1}>(n+1)^4$, assuming that $2^n>n^4$ and, as noted, $n\ge 17$. Let's estimate $2^{n+1}-(n+1)^4$:

$$2^{n+1}-(n+1)^4=\big(2^n-[(n+1)^4-n^4]\big)+(2^n-n^4)>(2^n-n^4)+(2^n-n^4)>0$$

To show the first inequality we have to check: $$(n+1)^4-n^4<n^4$$ but

$$\left(\frac{n+1}n\right)^4\le\left(\frac{18}{17}\right)^4<2$$

ajotatxe
  • 65,084
0

Using the function $x^{1/4}$ is not a purely algebraic proof. Here is one. Explicitely, we'll prove $2^n>n^4$ for all $n>16$.

For that, we'll prove by induction that if $n\ge 16$ and $2^n\ge n^4$, then $2^{n+1}>(n+1)^4$.

For $n=16$, we have an equality: $2^{16}=16^4$.

Now suppose that, for some $n\ge 16$, we have $2^n>n^4$. Then $2^{n+1}=2\cdot 2^n\ge 2n^4$. So we have to prove $2n^4>(n+1)^4$, i.e. $$n^4>4n^3+6n^2+4n+1.$$ As $n>1$, $\;4n^3+6n^2+4n+1>4n^3+6n^3+4n^3+n^3=15n^3$.

So it is enough to prove $n^4>15n^3$, which is equivalent to $n>15$. We've supposed $n\ge 16$.

Barry Cipra
  • 79,832
Bernard
  • 175,478
  • thanks, this is a much better solution! – JJTO Aug 15 '16 at 21:51
  • Using the fourth root of $2$ seems algebraic to me. For the purpose of the induction (modulo starting with the right base case!), it suffices to show that $2^{1/4}\gt7/6$. This can be done as follows: $2^3\cdot3^4=8\cdot81=648\gt625=5^4$ implies $2 \cdot 6^4=2^2(2^3\cdot3^4)\gt2^2\cdot 5^4=(2\cdot 5^2)^2\gt(7^2)^2=7^4$ – Barry Cipra Aug 15 '16 at 21:53
  • You can't prove algebraically that roots exist. It requires tools from calculus. I agree localising a fourth root can be done by some algebraic computation, but the IVT is at work behind the scene. – Bernard Aug 15 '16 at 22:15
  • @jj86 If you find this answer most useful / actually answers your question, then you can do everyone a favor by accepting it--this lets the community know you are essentially "done" with your question and gives the answerer due acknowledgment. – Daniel W. Farlow Aug 15 '16 at 22:51
  • @Bernard, point well taken. Do I understand correctly then that even $\sqrt2$ is disallowed in a purely algebraic proof? – Barry Cipra Aug 15 '16 at 23:38
  • In algebraic number theory, you can because the construction is done through the splitting field of a polynomial, which is a purely algebraic construction (a quotient of the ring of polynomials). But you can't say a proof is ‘algebraic’ if it rests more or less explicitly, on the I.V.T. – Bernard Aug 15 '16 at 23:48
0

Here is a nice little non-induction proof that $n^4\lt2^n$ for $n\gt16$.

Note that

$$n^4=\left(\sqrt n\over2\right)^8\cdot2^8\cdot1^{n-16}$$

So if $n\gt16$, the arithmetic-geometric mean inequality tells us

$$\sqrt[n]{n^4}\lt{8\cdot\left(\sqrt n\over2\right)+8\cdot2+(n-16)\cdot1\over n}={4\over\sqrt n}+1\lt2$$

hence $n^4\lt2^n$.

(Remark: for $n=16$ both inequalities in the displayed expression become equalities. In particular, all $16$ terms in the AGM product $\left(\sqrt4\over2\right)^8\cdot2^8$ are equal to $2$. For $n\lt16$, the AGM connection falls apart, as it must, since the inequality goes the other way.)

Barry Cipra
  • 79,832