How would you prove inequality $2^n \gt n^{10}$ using induction

Question

For the base case I can put a number such as $100$ for $n$ so $2^{100}\gt 100^{10}$.

Ok so now the induction hyp:

$2^{n+1} > (n+1)^{10}$ for $n \gt 101.$

where do I go from here? Also do I have to prove $2^{100}\gt 100^{10}$ ?

Answer 1

from $2^n>n^{10}$ we get by multiplying by $2$ $2^{n+1}>2n^{10}$ now it must be $2n^{10}>(n+1)^{10}$ this is equivalent to $n>\frac{1}{2^{1/10}-1}$ and this is true for $n\geq 14$

Answer 2

Suppose that $n^{10}<2^n$. We would like to show that:

$$(n+1)^{10}<2^{n+1}$$

For $n \geq 100$ you have $\frac{n}{100} \geq 1$, so:

$$(n+1)^{10} \leq (n+\frac{n}{100})^{10}=(\frac{101}{100})^{10}n^{10}$$

But $(\frac{101}{100})^{10}<2$ see Wolfram, so:

$$(n+1)^{10} \leq (n+\frac{1}{100})^{10}=(\frac{101}{100})^{10}n^{10}<2 n^{10}$$

But you know that $n^{10}<2^n$,so:

$$2 n^{10}<2 \cdot 2^n=2^{n+1}$$

Answer 3

If $n\ge100$, then by binomial expansion $$ \begin{aligned} (n+1)^{10}&=n^{10}+10n^9+45n^8+120n^7+210n^6+252n^5+210n^4+120n^3+45n^2+10n+1\\ &\le n^{10}+10n^9+(45+120+210+252+210+120+45+10+1)n^8\\ &=n^{10}+10n^9+1013n^8\quad\text{(as $n^k<n^8$ when $k<8$)}\\ &\le n^{10}+10n^9+11n^9\quad\text{(as $1013<11n$)}\\ &=n^{10}+21n^9\\ &<n^{10}+100n^9\\ &\le 2n^{10}. \end{aligned} $$ A simple induction gives the rest. If $n^{10}<2^n$ for some $n\ge100$, then the above shows that $$(n+1)^{10}<2n^{10}<2\cdot2^n=2^{n+1}$$ completing the inductive step. The base case $2^{100}>100^{10}$ is routine. For example, starting from $2^{10}=1024>10^3$ we immediately get that $2^{100}>10^{30}>100^{10}$.

Answer 4

We have $2^{n+1} = 2^n \cdot 2 \geq n^{10} \cdot 2$. From that we get $$(1+n)^{10} =\sum_{k=0}^{10}\binom{10}{k}n^k =n^{10} + \sum_{k=0}^{9}\binom{10}{k}n^k $$ and substracting $n^{10}$ from both sides left is to show that

$$\sum_{k=0}^{9}\binom{10}{k}n^k \leq n^{10},$$ dividing by $n^{10}$ obtains

$$\frac{10n^9}{n^{10}} + \frac{45n^8}{n^{10}} +\frac{120n^7}{n^{10}} +\frac{210n^6}{n^{10}} +\frac{252n^5}{n^{10}} +\frac{210n^4}{n^{10}} +\frac{120n^3}{n^{10}} +\frac{45n^2}{n^{10}} +\frac{10n}{n^{10}} +\frac{1}{n^{10}} \leq 1 $$ which is $$(*) =\frac{10}{n}+\frac{45}{n^2}+\frac{120}{n^3}+\frac{210}{n^4}+\frac{252}{n^5}+\frac{210}{n^6}+\frac{120}{n^7}+\frac{45}{n^8}+\frac{10}{n^9}+\frac{1}{n^{10}} \leq 1 $$ and since $n \geq 100$ we get $$(*) \leq \frac{10}{100}+\frac{45}{100^2}+\frac{120}{100^3}+\frac{210}{100^4}+\frac{252}{100^5}+\frac{210}{100^6}+\frac{120}{100^7}+\frac{45}{100^8}+\frac{10}{100^9}+\frac{1}{100^{10}} \leq 1$$ which can be verfied by calculating it. This completes the proof.

Answer 5

We can prove that $$2^n > n^{10} \implies 2^{n+1} > (n+1)^{10}$$ if we can show that $${2^{n+1}\over 2^n} > {(n+1)^{10}\over n^{10}}$$

When that inequality is true, then the above implication will necessarily be true. Simplifying: $${2^{n+1}\over 2^n} = 2$$ $${(n+1)^{10} \over n^{10}} = \left({n+1\over n}\right)^{10}$$ and $$2 > \left({n+1\over n}\right)^{10} \implies \left({n+1\over n}\right) < 2^{\ 0.1} \approx 1.072 \implies n \ge 14$$

So, for $n \ge 14$, we have $2^n > n^{10} \implies 2^{n+1} > (n+1)^{10}$.

To start our proof by induction, we need to find a starting value, a value for $n$ where $2^n > n^{10}$.

This is true for $n = 59$: $2^{59} \approx 5.76 \times 10^{17}$, and $59^{10} \approx 5.11 \times 10^{17}$, so $2^{59} > 59^{10}$.

Since $59 > 14$, we have proven by induction that:

$$ \forall n \ge 59 : 2^n > n^{10}$$