Tricki
a repository of mathematical know-how

I have a problem about the convergence of a sequence

Each time you click on the sentence that best describes your problem, more text and/or further questions will appear.

My problem concerns finding the limit of an explicitly given sequence.

  • Is the sequence defined by means of a formula for the nth term, or is it defined in some less direct way, such as using a recurrence relation?
    • It's defined by a formula for the nth term.
      • Could you say in broad terms what the function for a_n is like?
        • a_n is a rational function of n, that is, a function of the form p(n)/q(n), where p and q are both polynomials.
          • In that case, all you need to do is to exploit the following facts. If a_n\rightarrow a and b_n\rightarrow b, then a_n+b_n\rightarrow a+b, a_n-b_n\rightarrow a-b, \lambda a_n\rightarrow \lambda a, a_nb_n\rightarrow ab, and a_n/b_n\rightarrow a/b if b\ne 0. It helps to divide through by the largest power of n that appears in q. For instance, to prove that \frac{n^2+n}{n^2+5}\rightarrow 1, one rewrites it as \frac{1+1/n}{1+5/n^2} and applies the above rules to argue that the top and bottom tend to 1, so the whole fraction tends to 1. It should be noted that this argument freely uses the fact that 1/n\rightarrow 0 as n\rightarrow\infty. This is called the Archimedean property of the real numbers.
        • The expression for a_n involves a ratio of two functions that are more complicated than polynomials.
          • In that case you have a formula of the form a_n=f(n)/g(n), so you want to compare the growth rates of f and g as n tends to infinity. A few techniques can get you quite a long way. For example, if you can find some \rho>1 and prove that the ratio a_{n+1}/a_n is greater than \rho for every sufficiently large n, then a_n must tend to infinity. This, for example, is enough to show that a_n=2^n/n^{100} tends to infinity. To see this, note that 2^{n+1}/2^n=2, while (n+1)^{100}/n^{100}=(1+1/n)^{100}, which tends to 1 as n tends to infinity (because it is a product of 100 sequences, all of which tend to 1). Therefore, for sufficiently large n, a_{n+1}/a_n is bigger than 3/2. More generally, any exponential function c^n with c>1 grows faster than any polynomial function p(n). Combining this with techniques for dealing with rational functions will allow you to find limits of sequences such as a_n=\frac{n^2+n^3e^{-n</span>{n^2-72n-1}.
        • The formula for a_n involves raising a number to a power that depends on n.
          • There are various things you might have to do here. For instance, if you are asked to prove the obvious seeming fact that 2^{1/n}\rightarrow 1 as n\rightarrow\infty, then try turning the problem round: if 2^{1/n}>1+\delta, then (1+\delta)^n<2; however, the very simple but surprisingly useful inequality (1+\delta)^n\geq 1+n\delta proves that (1+\delta)^n>2 when n>1/\delta.
            If a_n is equal to some number close to 1 raised to a power that depends on n, then you will almost certainly want to make use of the fact that (1+1/n)^n\rightarrow e. For example, if you are asked for the limit of (1+3/n)^n, you can argue that it is the cube of (1+3/n)^{n/3} and hence that it tends to e^3. And (1+1/n^2)^n is the nth root of (1+1/n^2)^{n^2}, which is less than e (because in fact the sequence (1+1/n)^n is increasing), so it tends to 1 (because e^{1/n} tends to 1).
        • The formula for a_n involves factorials.
          • In that case, what you need to do depends on how delicate the problem is. Does it look as though a_n tends to 0 or to \infty?
            • Yes.
              • Then you may be able to get away with proving that a_{n+1}/a_n is bounded away from 1. For example, if a_n=n!/n^n, then a_{n+1}/a_n=(n+1)n^n/(n+1)^{n+1}=(n/(n+1))^n=1/(1+1/n)^n\rightarrow e^{-1}, which implies that a_n\rightarrow 0. Or you may consider using simple estimates for n! such as that n!\geq(n/e)^n, which actually follows from the above calculation if we observe that a_{n+1}/a_n=1/(1+1/n)>e^{-1} and a_0=1.
            • No (or don't know, or yes but it seems hard to prove).
              • In that case the problem is more delicate, and you may need to use Stirling's formula, which says that the ratio of n! to \sqrt{2\pi n}(n/e)^n tends to 1 as n tends to infinity.
    • It's defined by means of a recurrence.
      • There is one trick that is extremely useful in this situation, and it is sometimes even useful for determining limits of sequences where the nth term a_n is given by a formula, and that is first to prove that a limit exists, and then to use the recurrence to determine what the limit must be. An example will illustrate the idea. Suppose we define a sequence by taking a_0=2 and a_{n+1}=a_n/2+1/a_n. If we know that this sequence tends to a limit a, then both a_n and a_n/2+1/a_n must tend to a (since a_{n+1} also tends to a). But a_n/2+1/a_n tends to a/2+1/a, by the rules for adding and dividing limits, so a=a/2+1/a, which implies that a^2=2. Since every a_n is positive (by an easy induction), a=\sqrt{2}. However, we still need to prove that the sequence converges to something. How can we do this without simply proving that it converges to \sqrt{2}? The answer is that there are theorems (or axioms) that say that a sequence with such-and-such a property converges. For example, Cauchy sequences converge. For this particular problem, we use the fact that a monotone decreasing function that is bounded below converges. If we know that a_n>\sqrt{2}, then it is easy to check that a_{n+1}<a_n. But a_0>\sqrt{2} and t/2+1/t is greater than \sqrt{2} by the AM-GM inequality applied to t and 2/t. Therefore, the result is proved.

I have an explicitly given sequence, and am required to prove that it converges, but I am not required to calculate the limit.

  • In that case, you should consider finding the limit anyway, and you should also consider the techniques for proving convergence of sequences where all you are told is that they satisfy certain properties.

I am supposed to prove rigorously a statement that looks utterly obvious, such as that 2^{-n} or n^{-1} tend to 0.

  • Such questions look a bit confusing to begin with, but the point is to deduce them from the axioms for a complete ordered field. The simplest technique is the one suggested on this page for dealing with sequences defined by recurrences: argue first that your sequence tends to a limit and then think about what the limit must be. For example, the sequence n^{-1} is monotone decreasing and bounded below by 0, so it converges to some limit (which must be non-negative). If this limit is x and x\ne 0, then there must be some n such that 1/n<2x, which implies that 1/m<x/2 whenever m>4n. But this contradicts the fact that 1/n tends to x. A similar argument works for 2^{-n}.

My problem is to prove that a sequence converges, but rather than being told what the sequence is I just know that it has certain properties.