2 to the n is Greater than n Cubed when n is 10 and above
Jump to navigation
Jump to search
Theorem
- $\forall n \in \Z, n \ge 10: 2^n > n^3$
Proof
Proof by induction:
For all $n \in \Z$ such that $n \ge 10$, let $P \left({n}\right)$ be the proposition:
- $2^n > n^3$
We note that:
- $2^9 = 512 < 729 = 9^3$
so when $n < 10$ the proposition does not hold.
Basis for the Induction
$P \left({10}\right)$ is the case:
- $2^{10} = 1024 > 1000 = 10^3$
so $P \left({10}\right)$ is seen to hold.
This is our basis for the induction.
Induction Hypothesis
Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 10$, then it logically follows that $P \left({k + 1}\right)$ is true.
So this is our induction hypothesis:
- $2^k > k^3$
We need to show that:
- $2^{k + 1} > \left({k + 1}\right)^3$
Induction Step
This is our induction step:
We note that when $k \ge 10$:
\(\ds \left({1 + \dfrac 1 k}\right)^3\) | \(=\) | \(\ds 1 + \frac 3 k + \frac 3 {k^2} + \frac 1 {k^3}\) | Binomial Theorem | |||||||||||
\(\ds \) | \(\le\) | \(\ds 1 + \frac 3 {10} + \frac 3 {100} + \frac 1 {1000}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1 + \frac {300 + 30 + 1} {1000}\) | ||||||||||||
\(\text {(1)}: \quad\) | \(\ds \) | \(<\) | \(\ds 2\) |
Thus:
\(\ds 2^{k + 1}\) | \(=\) | \(\ds 2 \times 2^k\) | ||||||||||||
\(\ds \) | \(>\) | \(\ds \left({1 + \dfrac 1 k}\right)^3 2^k\) | from $(1)$ | |||||||||||
\(\ds \) | \(>\) | \(\ds \left({1 + \dfrac 1 k}\right)^3 k^3\) | Induction Hypothesis | |||||||||||
\(\ds \) | \(=\) | \(\ds k^3 + \frac {3 k^3} k + \frac {3 k^3} {k^2} + \frac {k^3} {k^3}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds k^3 + 3 k^2 + 3 k + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \left({k + 1}\right)^3\) |
So $P \left({k}\right) \implies P \left({k + 1}\right)$ and the result follows by the Principle of Mathematical Induction.
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.1$: Mathematical Induction: Exercise $10$