How to prove a sequence converges: Epsilon-N proofs.
I’ve previously written on how to prove that a function has a limit. In this post I’m going out of order, and backtracking to the question of how to prove that a sequence has a limit. The advice has strong overlap:
Make sure you have the definition committed to memory—so much so that it lives in your bones, and you can recite it if a troll leaps out from a bush and demands to know the definition.
In mathy English the definition is
> Let \((x _ n)\) be a sequence of real numbers, and \(L\) a real number. We say that \(L\) is the limit of \((x _ n)\) if for all \(\varepsilon > 0\) there exists an \(N\in\Bbb N\) such that for all \(n > N\) we have \(|x _ n-L|<\varepsilon\). In that case we write \(\lim _ {n\to\infty} x _ n = L\).
In “logish” (logicy English) it’s
$$ \forall \varepsilon >0, \exists N\in\Bbb N, \forall n\in\Bbb N, $$
$$ n > N \Rightarrow |x _ n - L| < \varepsilon $$(Note: Your class may instead use \(n\ge N\) rather than \(n > N\). It turns out that this difference doesn’t matter, so don’t worry about it if your class or textbook uses in inclusive inequality.)
Always write “Let \(\varepsilon > 0\).” Actually write it, don’t just think it. This is part of the process of working out the proof, not just part of the final answer.
After that, always write “Let \(N = …\)” What you put in place of the “…” is the hard part of the proof. In my earlier post on limits, the role of \(\delta\) there is similar to the role of \(N\). Therefore the entire point of the rest of the proof, is to identify what N is. Make sure you write that somewhere in your proof—preferably, immediately after writing “Let \(\varepsilon>0\).”
How do you find N? As this is the hard part, we’ll discuss it at some length. I won’t try to give a general recipe, since one doesn’t exist. But at least for the easier, more introductory limits, there is some guidance that I can give. If there is interest in medium- or hard-difficulty proofs of limits, leave a comment with some details and I can think of a follow-up blog post for those.
Examples
Always best to start with examples. I’ll give the full and completed proofs first. I’ll reflect on these, and try to generalize some advice later.
\(\frac 1 n \)
$$ \lim _ {n\to\infty} \frac 1 n = 0 $$
Proof: Let \(\varepsilon > 0\). Set \(N = \lceil \frac 1 \varepsilon \rceil\). Then let n be a natural number such that \(n\ge N\). Then \(n > \frac 1 \varepsilon\) and therefore \(\frac 1 n < \varepsilon\).
Now we have
$$ \begin{aligned} |x _ n-0| &=\left |\frac 1 n\right| \\ &= \frac 1 n \\ &< \varepsilon \end{aligned} $$
This proves that the definition of \(\lim _ {n\to \infty} \frac 1 n = 0\) is satisfied.
\(\Box\)
\(\frac{2n^2-1}{n^2+n+1}\)
$$ \lim _ {n\to\infty} \frac {2n^2-1}{n^2+n+1} =2 $$
Proof: Let \(\varepsilon > 0\). Set \(N = \lceil 5/\varepsilon\rceil\). Then if n is a natural number such that \(n > N\), we have \(n > 5/\varepsilon\) and therefore \(\varepsilon > 5/n\).
Therefore
$$\begin{aligned} |x_n-2| &= \left|\frac{2n^2-1}{n^2+n+1} -2\right| \\&= \left| \frac{2n^2-1-2(n^2+n+1)}{n^2+n+1 }\right| \\ &= \left|\frac{-2n-3}{n^2+n+1}\right| \\ &= \frac{2n+3}{n^2+n+1} \\ &< \frac{5n}{n^2} \\ &= \frac 5 n \\ &< \varepsilon \end{aligned} $$
This shows that the definition of \(\lim _ {n\to\infty} \frac{2n^2-1}{n^2+n+1} =2\) is satisfied.
\(\Box\)
\(\frac{\sin n}{n}\)
$$ \lim _ {n\to\infty} \frac{\sin n}{n} = 0 $$
Proof: Let \(\varepsilon > 0\). Set \(N = \lceil 1/\varepsilon\rceil \). Then for any natural number n such that \(n > N\) we have \(n > \frac 1 \varepsilon\) and therefore \(\varepsilon > \frac 1 n\).
Therefore
$$\begin{aligned} |x _ n - 2| &= \left|\frac{\sin n}n - 0\right| \\ &= \frac{|\sin n|}{n} \\ &\le \frac{1}{n} \\ &< \varepsilon \end{aligned} $$
This shows that the definition of \(\lim _ {n\to\infty} \frac{\sin n}n =0\) is satisfied.
\(\Box\)
Reflections
One thing you’re likely to notice is that you’re going to need to be handy with your algebra. We do a bunch of algebraic manipulations without comment, like going from \(\left|\frac{2n^2-1}{n^2+n+1} -2\right|\) to \( \left| \frac{2n^2-1-2(n^2+n+1)}{n^2+n+1 }\right|\). If that at all confuses you, then you need to practice your algebra.
You’re going to need to reason about absolute values. This isn’t hard but I’m still commenting on it anyway: For example you should recognize that since \(n\) is always a positive number, therefore \(|n| = n\). Similarly we have \(|-2n-3| = 2n+3\).
The really hard part, is knowing how to do “good approximations”. A step in the earlier calculations that likely caused a lot of confusion, was \(\frac{2n+3}{n^2+n+1} < \frac{5n}{n^2}\). How does this make sense?
I don’t like the \(2n+3\) on the top because it’s not simple. In particular I wish I could drop the “+3” part so that I have just one term, which would make things much easier.
Because \(n > 0\) then I can subtract 3 and add \(3n\), which will make my quantity bigger but simpler. Bigger is ok, as long as it’s not “too much bigger”. You tend to get a feeling for what’s “too much bigger” from practice. In this case going from \(2n\) to \(5n\) is not too much bigger. As a rough rule of thumb, it’s ok to make your “low degree terms” bigger, as long as you don’t increase the overall degree. In this example, 3 is a “low degree term” because its degree is zero while the other term \(2n\) has degree one. It’s ok to increase 3 to \(3n\) because I don’t increase the overall degree of the numerator.
So since I’m comfortable with subtracting 3 and adding \(3n\), then I get \(2n+3 < 2n+3-3+3n = 5n\). That’s the approximation I used in the numerator.
In the denominator things were even simpler: I can do approximations by again manipulating the low-degree terms. Here the highest degree term is \(n^2\) so I can manipluate all the other terms of lower degree, the \(n\) and 1.
Because I’m working in the denominator, I want to approximate by decreasing the denominator, therefore increasing the value of the enter fraction. Therefore I merely subtract the n and 1. This now explains how I got
$$ \frac{2n+3}{n^2+n+1} < \frac{5n}{n^2} $$
Approximations like this are curcial throughout real analysis, and it’s one of the main skills that you will have very little experience with before taking real analysis, but will need to acquire and use all the time throughout the course. So try to get good at these with lots of practice.Note the use of the approximation \(\frac {|\sin n|}n \le \frac 1 n \). Again, this is a common approximation, coming from the fact that \(-1\le \sin x\le 1\) for all \(x\in\Bbb R\). This will be frequently useful, so be ready for it!
Exercise
Prove
$$ \lim_{n\to \infty} \frac{1}{n^2} = 0 $$
$$ \lim_{n\to\infty} \frac{n+1}{n^2+n} = 0 $$
$$\lim_{n\to\infty} \frac{n^2+n+1}{n^2+n} = 1$$