1
$\begingroup$

I have 2 exercises that I think are related to each other. I think they should be proved by mathematical induction. They are:

  • prove that: limit of n which approaches infinity $(2^n / n!) = 0$

  • prove that: limit of n which approaches infinity $(n^2 / 2^n) = 0$

There is an hint for the second one: show using induction that $2^n ≥ n^3$ for all $n ≥ 10$

Well, surely I have to repeat a bit theory about limits and, in particular, about limits at infinity - I have already started doing it - but I hope that I will complete my review of them after finished this exercise.

I think that infinity divided by infinity is undefined but when we are speaking about the limiting process, therefore trying to answer to the question: "what happens to our variable when it approaches infinity?", we can end up with another, definite answer...I think usually (or always?) zero, infinity or minus infinity.

I think that in the division it should be important also to establish which one between numerator and denominator is larger, as if the numerator is smaller than the denominator, we get smaller number than when the numerator is larger than the denominator...yet, in this case the answers to both the limit operations are zero...I start making confused myself!

However, I have the hint which tells me that the denominator of the second equation is larger than its numerator and I think it is the same for the first equation. Namely, n factorial is definitely larger than $2^n$. Thus, maybe do I have to show by mathematical induction that in both cases the denominator is bigger than the numerator?

Also, perhaps, should I link these thoughts with the fact that we have 2 quotients with n expressed either as a base and as an exponent and thinking about this distinction?

By the way, I find these problems very fascinating for all the abstraction which involves the concepts related to the limits at infinity and limits and infinity themselves.

$\endgroup$
6
  • $\begingroup$ why no answers this time? I am upset... $\endgroup$ Oct 28, 2015 at 12:03
  • $\begingroup$ Your question is too long! :) Let me read it! :) $\endgroup$ Oct 28, 2015 at 14:05
  • 2
    $\begingroup$ "I think usually (or always?) zero, infinite or minus infinity." Simple counterexample: $\lim_{n\to\infty}1$. Less stupid counterexample: $\lim_{n\to\infty}\frac{n+1}n$. $\endgroup$ Oct 28, 2015 at 14:21
  • $\begingroup$ You'll need induction to prove that $2^n\ge n^3$ for $n\ge10$. $\endgroup$ Oct 28, 2015 at 14:22
  • $\begingroup$ @H.R. yes, it is long but I want to show that I have thought about it. Otherwise, someone might say that I am asking for help without putting any effort by my side. $\endgroup$ Oct 28, 2015 at 16:39

1 Answer 1

1
$\begingroup$

OK, the general strategy to deal with this kind of problems is to use the squeezing theorem. This theorem states that

$$if\,\,\,\,\left\{ \matrix{ {l_n} \le {a_n} \le {u_n}, \,\,\,\,\,\,\,\,\,\ n \ge N \hfill \cr \mathop {\lim {l_n}}\limits_{n \to \infty } = L \hfill \cr \mathop {\lim {u_n}}\limits_{n \to \infty } = L \hfill \cr} \right.\,\,\,\,\,\,then\,\,\,\,\,\,\,\mathop {\lim {a_n}}\limits_{n \to \infty } = L\tag{1}$$

I think you have no problem to prove by induction that

$${2^n} \geqslant {n^3},\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,n \geqslant 10\tag{2}$$

Now, consider the following

$$\frac{1}{{{2^n}}} \leqslant \frac{1}{{{n^3}}}\,\,\,\,\,\,\,\,\, \to \,\,\,\,\,\,\,\,\,\,\frac{{{n^2}}}{{{2^n}}} \leqslant \frac{1}{n}\,\,\,\,\,\,\,\,\, \to \,\,\,\,\,\,\,\,\,\,\,0 < \frac{{{n^2}}}{{{2^n}}} \leqslant \frac{1}{n},\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,n \geqslant 10\tag{3}$$

also, you know that

$$\eqalign{ & \mathop {\lim }\limits_{n \to \infty } \frac{1}{n} = 0 \cr & \mathop {\lim }\limits_{n \to \infty } 0 = 0 \cr}\tag{4}$$

finally, using the squeezing theorem you can conclude

$$\mathop {\lim }\limits_{n \to \infty } \frac{{{n^2}}}{{{2^n}}} = 0\tag{5}$$

I will leave the other example for you to prove. The strategy is totally the same. :)


Proof of $(2)$ by induction

you can check by putting $n=1,2,3,...,9$ that ${2^n} \geqslant {n^3}$ is false except for $n=1$. So the starting point for our induction will be $n=10$ for which ${2^n} \geqslant {n^3}$ is true. Next, we are hoping that this would be true for $n>10$. Hence we make the following claim to be true

$${2^n} \geqslant {n^3}, \,\,\,\,\,\,\,\,\,\, n\ge10$$

To prove our claim we assume that it is true for $n=k$ and prove it will hold for $n=k+1$. So by the induction assumption ${2^k} \geqslant {k^3}$ is true. We start with this assumption and do some algebraic manipulations

$$\begin{array}{l} {2^k} \ge {k^3}\\ {2.2^k} \ge 2.{k^3}\\ {2^{k + 1}} \ge 2{k^3} \end{array}$$

Now, if I could prove that $2{k^3} \ge {\left( {k + 1} \right)^3}$ then it would be followed that

$$\eqalign{ & {2^{k + 1}} \ge 2{k^3} \ge {\left( {k + 1} \right)^3} \cr & {2^{k + 1}} \ge {(k + 1)^3} \cr} $$

and hence the proof would be finished. So it seems reasonable to focus on my wish ,i.e, to prove $2{k^3} \ge {\left( {k + 1} \right)^3}$. For this purpose, consider the following

$$\begin{array}{l} 2{k^3} \ge {(k + 1)^3}\\ 2{k^3} - {(k + 1)^3} \ge 0\\ \begin{array}{*{20}{l}} {{k^3} - 3{k^2} - 3k - 1 \ge 0}\\ {{{\left( {k - 1} \right)}^3} - 6k \ge 0}\\ {{{\left( {k - 1} \right)}^3} - 6\left( {k - 1} \right) - 6 \ge 0}\\ {\left( {k - 1} \right)\left( {{{\left( {k - 1} \right)}^2} - 6} \right) - 6 \ge 0} \end{array} \end{array}$$

So the whole above inequalities are equivalent and I can just prove the last one is true by using $k\ge10$. This is how it works

$$\begin{array}{l} \left\{ \begin{array}{l} k \ge 10\,\,\, \to \,\,\,k - 1 \ge 9\\ k \ge 10\,\,\, \to \,\,\,{\left( {k - 1} \right)^2} \ge 81\,\,\, \to \,\,\,{\left( {k - 1} \right)^2} - 6 \ge 75 \end{array} \right.\\ \left( {k - 1} \right)\left( {{{\left( {k - 1} \right)}^2} - 6} \right) \ge 9 \times 75 = 675\\ \left( {k - 1} \right)\left( {{{\left( {k - 1} \right)}^2} - 6} \right) - 6 \ge 669 \ge 0 \end{array}$$

this completes the proof.

$\endgroup$
18
  • $\begingroup$ Thank you for your answer! Actually, I have problems for the mathematical induction proof as well. I have just began studying real analysis.PS. More exactly, does the squeeze theorem assert that if there is a function greater-equal than another function and smaller-equal than another function, and the 2 other functions are defined at a point and their limit coincides at that point, then the limit of the function in between is the same(?)If yes, this is true for any kind of limits which equals any given value- I mean,not only for limits at infinity which equal zero - as in our case. Am I right? $\endgroup$ Oct 28, 2015 at 17:30
  • $\begingroup$ Yes, you are right! :) That was a good point you mentioned. I will edit the answer. Shall I write down the proof for mathematical induction? :) $\endgroup$ Oct 28, 2015 at 17:41
  • $\begingroup$ Well, if you can help as much as possible, in this case, I really would appreciate it! $\endgroup$ Oct 28, 2015 at 17:44
  • 1
    $\begingroup$ @Alwayslearning: Of course, there is no need for the other two functions to be defined at that point! The only thing matters is the existence of their limit at that point! :) $\endgroup$ Oct 28, 2015 at 17:44
  • $\begingroup$ @Alwayslearning: I will write you down the induction thing but now I have to go! :) Maybe in the next two hours. :) $\endgroup$ Oct 28, 2015 at 17:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .