- #1
koroviev
- 2
- 0
Homework Statement
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].
Homework Equations
We need to use a proof by induction.
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].
Last edited: