Help solving an induction problem…$2^n < n!$ [closed]

Question

Prove the following by induction.

k and n in N (natural number)

$n^k < 2^n $

$2^n < n! $

Need hint and help please.

Thank you very much.

Answer 1

It is a good idea to check the factor by which the terms in question grow: For the middle term it is easy, it grows by a factor of $\frac{b_{n+1}}{b_n}=\frac{2^{n+1}}{2^n}=2$; for the term on the right, it grows by a factor of $\frac{c_{n+1}}{c_n}=\frac{(n+1)!}{n!}=n+1$; this is quickly larger than $2$, for example $n+1\ge 3$ for $n\ge 2$. The one on the left grows by $\frac{a_{n+1}}{a_n}=\frac{(n+1)^k}{n^k}=\left(1+\frac1n\right)^k=\frac1{\left(1-\frac1{n+1}\right)^k}$. From the Bernoulliy ineqquality, we have $\left(1-\frac1{n+1}\right)^k\ge 1-\frac k{n+1}$ and $n$ large enough this is close to $1$, specifically, $1-\frac k{n+1}>\frac23$ for $n\ge 3k$. We conclude that $\frac{a_{n+1}}{a_n}<\frac32$ for $n\ge 3k$. Thus with $n_0:=\max\{3k,2\}$ we have $$\tag1\frac{a_{n+1}}{a_n}<\frac23<\frac{b_{n+1}}{b_n}=2<3\le \frac{c_{n+1}}{c_n}\qquad\text{for all $n\ge n_0$}. $$ Now it may happen that $a_{n_0}\ge b_{n_0}$ and/or $b_{n_0}\ge c_{n_0}$. But there certainly exists $m_0\in\mathbb N$ such that both $a_{n_0}<3^{m_0} b_{n_0}$ and $b_{n_0}<\left(\frac32\right)^{m_0}c_{n_0}$: Just let $$m_0=1+\left\lceil\max\left\{\log_3\frac{a_{n_0}}{b_{n_0}},\log_{3/2}\frac{b_{n_0}}{c_{n_0}}\right\}\right\rceil.$$ In fact this gives us $a_{n_0}<3^{m} b_{n_0}$ and $b_{n_0}<\left(\frac32\right)^{m}c_{n_0}$ or simply $$\tag2 \left(\frac23\right)^ma_{n_0}<2^mb_{n_0}<3^mc_{n_0}\qquad\text{for all $m\ge m_0$}.$$ By induction on $m$ using $(1)$, we find that $$ \tag3a_{n_0+m}\le \left(\frac23\right)^ma_{n_0}\qquad\text{for all $m\in\mathbb N$}$$ and $$\tag4 c_{n_0+m}\ge 3^mc_{n_0}\qquad\text{for all $m\in\mathbb N$}.$$ Combining $(2)$, $(3)$, $(4)$ we finally obtain $$ a_n<b_n<c_n\qquad\text{for all $n\ge n_0+m_0$}.$$

Answer 2

Work “backwards”: what do I need in order for the induction step to succeed?

Suppose $n^k<2^n$; then $$ 2^{n+1}=2\cdot 2^n>2n^k $$ and we'd like that $2n^k\ge(n+1)^k$ or $n\sqrt[k]{2}\ge n+1$, that means $$ n\ge\frac{1}{\sqrt[k]{2}-1} $$ So, whenever $n$ satisfies this condition, the induction step can be performed. It remains to see whether we find a base step (the “sufficiently large $n$”). (Thanks to eudes for suggesting an elementary method.)

It's easy to see that $n<2^n$, for all $n$; then $$ n^k<2^n $$ for $n=4k^2$, because $$ n^k=(4k^2)^k=(2k)^{2k}<(2^{2k})^{2k}=2^{4k^2}=2^n $$

Similarly, if $n!>2^n$, we have $(n+1)!=(n+1)\cdot n!>(n+1)2^n\ge 2^{n+1}$ as soon as $n+1\ge 2$. However $n<4$ doesn't work, but $n=4$ does, because $2^4=16$ and $4!=24$.

Answer 3

Let $k \in \mathbb N$ be given. The sequence $\{\frac{\ln n}{n} \}$ converges to $0$. So, there exists $n_0 \in \mathbb N$ (sufficiently large) such that $\frac{\ln n_0}{n_0} < \epsilon = \frac{\ln 2}{k}$. Which means that $n_0 ^k <2^{n_0}$. Now that we guaranteed the existence of such an $n_0$, let $n_0 = \min \{ t \in \mathbb N, t ^ k < 2^t \}$. Our base case will be $n = n_0$.

Inductive step:

Note that the sequence $\{\frac{\ln n}{n} \}$ is decreasing. Then,

$$n^k < 2^n \implies \frac{\ln n}{n} < \frac{\ln 2}{k} \implies \frac{\ln (n+1)}{n+1} < \frac{\ln 2}{k} \implies (n+1)^k < 2^{n+1}$$

For the second inequality: the base case is $n=4$. The inductive step is really easy to do. Finally, we conclude that the inequality holds for all $n \ge \max\{n_0,4\}$.

Answer 4

The first inequality without induction: if $m\geqslant2k-1$ then $$ \begin{aligned} 2^m&=(1+1)^m\\&>\binom{m}{k}\\&=\dfrac{m(m-1)\cdots(m-k+1)}{k!}\\&>\dfrac{(m/2)(m/2)\cdots(m/2)}{k!}\\&=\dfrac{m^k}{2^kk!}\end{aligned}.$$ Now, let $t$ be the integer such that $2^t\leqslant k!<2^{t+1}.$ Then $$\tag{1}m^k<2^{m+k}k!<2^{m+k+t+1}$$ as long as $m\geqslant2k-1$ (the idea here is that $m>m-1>\cdots>m-k+1>m/2$ whenever $m\geqslant2k-1$).
If $n\geqslant k+(2k-1)+(t+1)=3k+t$ then $$2^n>n^k.$$

For the second inequality, note that $2^4<4!$ and suppose that $2^n<n!$ as long as $n>3.$ Then $$2^{n+1}=2^n\cdot2<n!\cdot2<n!\cdot(n+1)=(n+1)!.$$