2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ @HagenvonEitzen Sorry,actually I din't notice that ! $\endgroup$ – Arpit Kansal Sep 14 '15 at 20:05
  • 1
    $\begingroup$ Is there anything missing? It says "five statements", but there are only two, and a third one, which follows from the two. Also, and more importantly, do you know how to prove by induction? How would you start such a proof? $\endgroup$ – eudes Sep 14 '15 at 20:15
  • $\begingroup$ Also, is it for every $k$ (positive)? $\endgroup$ – eudes Sep 14 '15 at 20:27
  • $\begingroup$ @eudes Sry that was a typo Yes i do know how to do induction and yes for every k (positive) I would have started with n=1, but apparently that does not work, because the problem is saying sufficiently large. $\endgroup$ – question Sep 14 '15 at 20:43
  • $\begingroup$ Proof for the inequality between $2^n$ and $n!$ can be found in many older posts on this site. Have a look here and also at other questions linked there. $\endgroup$ – Martin Sleziak Sep 15 '15 at 8:03
2
$\begingroup$

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$}.$$

$\endgroup$
1
  • $\begingroup$ Some serial downvoter found this page, it seems. $\endgroup$ – egreg Sep 15 '15 at 7:41
2
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ I like this answer the most, because it's the most elementary for what's clearly a pre-calculus exercise. My only objection is the use of $\lim2^n/n^k$, because it might be too advanced, and more importantly: how shall we calculate the limit, if not by this inequality? But if we prove $n^2<2^n$ for $n\geq 5$ first (in fact only for $5$, if we have 2nd step for every $k$), we can get 1st step quite easily with $n_0=k\max(5,k)\sim k^2$: $$ (k\max(5,k))^k<(\max(5,k)^2)^k<2^{\max(5,k)\cdot k} $$ You can do even better, and still elementary, but this won't fit here, and I can't write an answer now. $\endgroup$ – eudes Sep 18 '15 at 14:28
  • $\begingroup$ @eudes The limit can be proved by a straightforward application of l'Hôpital. But I'll try and add an elementary argument. $\endgroup$ – egreg Sep 18 '15 at 14:37
  • $\begingroup$ Of course, but I just doubt that if you ask such a question, you know l'Hôpital. Also, (sorry for that) I meant actually, if going from scratch, like in a textbook, we'd rather prove the limit by the inequality. And, be my guest, you can use the one from my comment. Another, but with higher 1st step: $$ (4k^2)^k = (2k)^{2k} < (2^{2k})^{2k} $$ where $n<2^n$ is necessary. $\endgroup$ – eudes Sep 18 '15 at 14:54
1
$\begingroup$

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\}$.

$\endgroup$
1
$\begingroup$

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)!.$$

$\endgroup$
3
  • $\begingroup$ Thank you C.I.J but I have some questions: Where did the m>_ 2k -1 came from $\endgroup$ – question Sep 14 '15 at 21:14
  • $\begingroup$ You mean what is the motivation behind it? $\endgroup$ – CIJ Sep 14 '15 at 21:16
  • $\begingroup$ There is a proof that uses almost the same argument in Rudin's Principles of Mathematical analysis to prove that if $x$ is real and $0<a<1$ then $\lim\limits_{n\to\infty}n^xa^n=0$ $\endgroup$ – CIJ Sep 14 '15 at 21:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.