I have a question regarding an assignment in school. We are learning about limit, epsilon-delta proofs. This is an assignment that I have done but still need to correct.
a) Give a proper definition of what it means for a general sequence $$\lim_{x\to\infty} a_n = \infty$$
b) Recall $ n! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot \cdot \cdot n $ Use the definition from a) to show that $n!$ grows faster than $2^n$. That is, show that; $$ \lim_{n\to\infty} \frac{n!}{2^n} = \infty $$
Ok so there is what I did the first time handing it in. I compared the ratio to show that $a_{n+1} > a_n $ Which we could not use according to my teacher since we have not proved ratio or done them in class yet.
I know for an expression to go towards infinity it must not be bounded from above and it must be increasing as the n gets larger. I hafto use my definition in a) and also I have stated another definition in b). That is the definition of an increasing sequence wich is, if increasing:$$ a_{n+1} > a_n $$ I have been trying to use induction and I can show with induction that $ n! > 2^n \forall n \geq 4$ But this according to my teacher is not proof enough that the sequence is going towards infinity when n is going to infinity. I know I am supposed to use induction, but how? I also know that I hafto use my definition from a) and that I should start with: Let $ \varepsilon > 0 $ be given (fixed but unknown). My teacher showed this information:
He said to use $1) a_n \geq \frac{n}{4}$ ok! and $n\geq 1$. Or we could use $2) a_n \geq \frac{n}{2}$ ok, and $n \geq 2$. Or third, we could also use $3) a_n \geq n$ ok and $n \geq 6$ We will hafto prove it and I would assume induction would be a good proof? Start with basecase, n = 4 (could choose any basecase but it has to be 1 or more in this case, if i'd choose 1)), then $$\frac{4 \cdot 3 \cdot 2 \cdot 1}{2^4} \geq \frac{n}{4}$$, which is ok. Then after this i would hafto do induction step, where I assume that it holds for n = k and then it would also hold for n = k + 1. But here Im insecure about exactley what I do. I know I need to prove the induction hypothesis, but exactley what would be the induction hypothesis. Do I prove this???; $$\frac{k(k+1)!}{2^{k+1}} \geq \frac{(k+1)}{4}$$ And how exactly would the following computations look? I find the n! term hard to work with. After the induction proof I guess I also need to find an n, from the definition in a), so that $a_n > \varepsilon$. This I also find hard. I know that the formula should be $$ n \geq 4\varepsilon+1$$ This implies that $\frac{n}{4} > \varepsilon$, since $a_n \geq \frac{4}{n}$ we have, $a_n > \varepsilon$. A good choice when \varepsilon is uknown would then be $$N = 4 \varepsilon +1$$. I understand this reasoning and I understand that N can be made a function of epsilon. I understand epsilon is the challange and to prove the limit exists all challanges, epsilon, can be answered with this N, if the limit is infinity (although infinity is not a number, so the sequence is not convergeing, but divergeing when it goes towards infinity) the expression can with this N always be made larger than any epsilon. My problem is the algebra. How do I find this N? The induction proof, how do I prove that it holds for n=k+1?? I think i have problems overall just getting the assignment to sync and really be sure that I have used the defn. in a accurate, that I hve proven the sequence is growing and that it is going towards infinity. I'ts like I'm almost there and understand it, but there is still some part missing. I think mainly it's the n! term that is giving me problems. If I had $\frac{n+1}{2} > \varepsilon \leftrightarrow n+1 > 2\varepsilon \leftrightarrow n > (2\varepsilon) - 1$. Here the n would have been very easy to compute. Oh well, now it is'nt. So help is much wanted and needed ! :)
The Inequality: For the induction step, suppose $k\ge 4$ and we know that $\frac{k!}{2^k}\gt \frac{k}{4}$. We want to show that $\frac{(k+1)!}{2^{k+1}}\gt \frac{k+1}{4}$. We have $$\frac{(k+1)!}{2^{k+1}}=\frac{k!}{2^k}\cdot \frac{k+1}{2}\gt \frac{k}{4}\cdot \frac{k+1}{2}=\frac{k}{2}\cdot\frac{k+1}{4}\gt \frac{k+1}{4}.$$
Finishing: Now that we have proved an appropriate inequality, we show that for any $B\gt 0$ there exists an integer $N$ such that if $n\gt N$ then $\frac{n!}{2^n}\gt B$.
Since $\frac{n!}{2^n}\gt \frac{n}{4}$, to make the ratio greater than $B$ it suffices to make $\frac{n}{4}\gt B$, or equivalently to make $n\gt 4B$. Choose $N=\lceil 4B\rceil$, where $\lceil x\rceil$ is the smallest integer which is $\ge x$.