(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

If [itex]k[/itex] is a natural number, prove that [itex]2^{n} > n^{k}[/itex] for all [itex]n \geq k^{2} + 1[/itex].

2. Relevant equations

We need to use a proof by induction.

3. The attempt at a solution

Let's do the case when [itex]k = 4[/itex]. We check the base case directly:

[tex]2^{17} = 131072 > 83521 = 17^4[/tex]

Suppose [itex]2^{n} > n^{4}[/itex] for some [itex]n \geq 17[/itex], we have that

[tex]2^{n+1} = 2 \cdot 2^{n} > 2 n^{4} = n^{4} + n^{4}[/tex]

Since [itex]n \geq 5[/itex], we have that

[tex]2^{n+1} > n^{4} + 5 n^{3} = n^{4} + 4 n^{3} + n^{3}[/tex]

Since [itex]n \geq 7[/itex], we have that

[tex]2^{n+1} > n^{4} + 4 n^{3} + 7 n^{2} = n^{4} + 4 n^{3} + 6 n^{2} + n^{2}[/tex]

Since [itex]n \geq 5[/itex], we have that

[tex]2^{n+1} > n^{4} + 4 n^{3} + 6 n^{2} + 5 n = n^{4} + 4 n^{3} + 6 n^{2} + 4 n + n[/tex]

Finally, since [itex]n \geq 1[/itex], we have that

[tex]2^{n+1} > n^{4} + 4 n^{3} + 6 n^{2} + 4 n + 1 = (n + 1)^{4}[/tex]

However, I cannot extend this method to a general [itex]k[/itex]. First, I have trouble with the base case:

[tex]2^{k^{2} + 1} > (k^{2} + 1)^{k}[/tex]

I tried to do this by induction on [itex]k[/itex], but didn't make much headway. My method for the inductive case also breaks down because for [itex]k \geq 8[/itex] the largest coefficient in the expansion of [itex](n + 1)^{k}[/itex] is larger than [itex]k^{2} + 1[/itex].

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Exponential grows faster than polynomial

**Physics Forums | Science Articles, Homework Help, Discussion**