Numerical evaluation

There is not very much one can do numerically (typically on a computer) with sequences. It is obviously impossible to check infinitely many individual things one by one (as computer does it) in a finite time, so for instance one cannot check infinitely many successive couples to confirm or rule out some kind of monotonicity. The same applies to boundedness.

How about limit? Is it possible to use computer to find out whether a given sequence has a limit and determine what is it? Unfortunately, it is not possible in general, again for the reason that computers cannot check infinitely many numbers. However, computers are still often used in this area, usually hoping that our problems are nice enough to be handled that way.
Typical procedure students try when given a sequence goes like this: They start putting in numbers for n, first small, then larger and larger, and check on results to see how they behave. If they, for instance, keep growing, a student would guess that the given sequence converges to infinity. On the other hand, if even for a very large number substituted for n, the sequence is not too large and the results do not change very much, a student would guess that the sequence converges and the number that keeps coming up is more or less the limit.

Indeed, a typical computer program for evaluating limits works exactly in this way. Very often one actually sees the following method used:

Pick a large number N, plug it into the sequence. Then plug in N +1. If a_N and a_N+1 have the first few meaningful decimals common, then those decimals are probably correct and they are the best estimate for the limit.

Sometimes, to be on the safe side, one compares the N-th term and the (N +10)-th term, or the N-th term and the (N +1000)-th term, one can also try comparing the N-th term and the (2N)-th term, and so on.

Unfortunately, none of the procedures outlined above works reliably. This is caused by several factors. One is the fact that the numbers that we put in are limited. For instance, on your typical calculator you cannot enter numbers larger than 10 raised to 99. Now that we have some experience, we can easily conceive a sequence that is even constant on its first 10⁹⁹ terms, and then does something wild. Obviously, there is no way to find out about it using a calculator that cannot handle such large numbers. Another reason for failure to guess properly using calculators is that the sequence is up to something, but it does it so slowly that we do not notice. Indeed, if you want to see a nice example of why the trick with comparing successive (or more-or-less successive terms) cannot work, see this note.

Still, we do see these procedures used. Why? Because there is nothing better. When we encounter a sequence, we hope that it is not one of the crazy ones, apply the tricks described above and hope that we are not too much off. That is, this is what we do if we cannot handle the situation theoretically. In the next two sections we actually show some situations when it is the numerical, not theoretical approach that we are interested in.

The numerical approach is safest when we also know something about the given sequence theoretically, that is, for sure. For instance, one can prove that for some types of sequences the trick with comparing successive terms really works.

You may argue that the above example - and indeed the whole point - had the underlying idea that a sequence may have some feature that happens very late in it, and the observer does not check far enough to actually see it happening. Surely if the observer was more patient, he would have discovered what is happening eventually. But that is exactly the point. A sequence is infinite, it can afford to wait before it starts doing something; you check it all the way up to n = 10¹⁰⁰, what if the sequence does something wild later? So you acquire a supercomputer and check all the way to n = 10¹⁰⁰⁰, but still you cannot be sure that even later something does not happen.

Still, examples like that are quite rare and you may hope that you do not stumble over them. However, there is another reason why computing technology has troubles with evaluating limits, even quite simple ones, which is related to rounding error and cannot be avoided. Consider the following problem:

This is a very nice sequence, and it is easy to show that it converges to infinity using the appropriate tricks, first getting rid of the roots (see the box "difference of roots") and then cancelling powers (see the box "polynomials and ratios with powers").

Now what happens if we try to evaluate this sequence using my calculator?

n:	10	100	500	1000	10,000	1,000,000
an:	4.999	50	250	500	0	0

What conclusion would you make based on this table? That the sequence converges to zero! We stopped when we substituted a million for n, but you would get zero for any other large number. How is it possible?

Every time a calculator or a computer needs to remember a real number, it only remembers the first several digits and how many digits there are altogether (the exponent), large numbers are typically written as, say, 3.174293⋅10¹⁹. For instance, your typical scientific calculator shows ten digits, but to be on the safe side, it remembers 12 digits. Now imagine what happens if you want to add 20 to the number 123456789123456789. Since my calculator remembers only how many digits there are and then the first twelve, it sees this large number as 123456789123******. If you add 20, it will get lost in the *** part, and the calculator still remembers the new number as 123456789123******. That is, if you add such a small number, to your calculator it makes no difference. One can then naturally expect wrong answers. For instance, the following calculation should obviously lead to 20, but we will see how my calculator sees it.

(123456789123456789 + 20) − 123456789123456789 = (123456789123****** + 20) − 123456789123****** = 123456789123****** − 123456789123******= 0.

Now that is exactly what is happening with the above sequence. Note that in the first term, we have n⁸ plus something, root from it all. If it wasn't for the something, the root would cancel the eighth power and you would end up with n⁴. This in turn would cancel with the "− n⁴" and the sequence would be zero. So the sequence is really given by the "+ n⁵" under the root. What happens if we try to substitute n = 10,000 = 10⁴ into the sequence on my calculator? We take the eighth power and get 10³², a number with 32 + 1 = 33 digits. Then we add to it (10⁴)⁵ = 10²⁰. But this makes difference only at the position 20 + 1 = 21 in that large number, that is, it does not reach to the first twelve digits remembered by the calculator. Thus the calculator does not notice that we added n⁵, which is why in the end it comes up with zero.

Now you may say, great, but if I had a better calculator that remembers 15 digits, it would work fine. And I say, yes, but only for n = 10,000. If you try n = 1,000,000, the difference between the large and small number gets much bigger and even your better calculator will not notice the addition. In the same way one can show that no matter how capable your computer is, as long as it remembers just parts of numbers (which all of them do when doing real number computations), it will eventually - for n large enough - fail to notice the addition. If you are curious, you can repeat the above analysis to show the following: If k is a natural number such that the computer remembers at most 3k digits of real numbers, then n = 10^k is already enough to fool it. In other words, n = 1,000,000 = 10⁶ would fool a computer that remembers 18 digits.

Is there a way out? There are programs which are really smart and work also with algebra (in particular they might know the trick with getting rid of roots), both Maple and Matematica did not get fooled by this example (but they may fail with a less obvious one). Another way to see what this sequence does is to use some knowledge of theory. For instance, I can figure out - even with my lousy calculator - how much is a_{1,000,000,000}. How? From our intuitive calculations it follows that in fact

You can see it like this:

Here we can even get a more precise statement. It is easy to check that the following inequalities are true:

This shows that the error of approximation is very small, since we have

that is, the error of approximation is at most 1/(4n²), which is a very small number. (An approximation of a_n can be also obtained using the Taylor polynomial). When you compare this with the values in the table above, you will see a very good fit up to n = 1000, before the calculator lost its way. Using this approximation we now easily figure out that a_{1,000,000,000} ∼ 500,000,000±1, and we did not even need that calculator for it. In fact, for such a large n the approximation is extremely precise, the maximal possible error is 0.0000000000000000025.

This whole note should be taken mainly as a warning. If you apply your calculator to a given sequence, the answers that are suggested may be far off. Still, for most sequences you do get good hints, so when we cannot handle a problem theoretically, we often try to get some insight using computers. For some interesting cases when the calculator approach does work, go to the next section.

Pi and Euler number
Back to Theory - Applications