## Tools: Geometric Sequences and Sums

Instead of jumping straight to an intuitive explanation of why you *can* do infinitely many tasks in a finite period of time,
I'd like to take a detour here and develop some of the math behind the intuition. Once we settle the motivating paradox we're going to take a look at some
related puzzles, and it will serve us well to be comfortable with the underlying mathematics.

A key concept is that of a *geometric sequence*: a sequence of numbers for which the ratio between any number and its predecessor is constant.
For example, the sequence of distances in Zeno's paradox, (50, 25, 12.5, ...), is a geometric sequence since the ratio between 25 and 50 is 1/2,
the ration between 12.5 and 25 is also 1/2, and so on down the whole sequence.

In fact, knowing the first number and the common ratio in a geometric sequence actually tells us everything about the whole sequence! If the first number in a
geometric sequence is *a* and the common ratio is *r*, then we can write every number in the sequence in terms of *a* and *r*:

(*a, ar, ar*^{2}, ar^{3}, ..., ar^{k}, ...).

From the above we see that the (*k*+1)st number in the sequence, call it *n*_{k+1}, is given by the formula:

*n*_{k+1} = *ar*^{k}.

**Exercise 1:** *Why don't the ks match? In other words, it seems more natural for the formula to say that the kth number is equal to ar*^{k}, rather than
the (k+1)st number being equal to this. Why isn't this the case?
In particular, in our previous example we had *a*=50 and *r*=1/2 so the 10th number in the sequence can be calculated:

*n*_{10} = *ar*^{9} = 50 · (1/2)^{9} = 50 · (1/512) = 0.09765625

This corresponds to the length of the 10th leg of the infinitely many runs you have to complete to go 100 meters.

**Exercise 2:** *Consider the sequence (27, 9, 3, 1, 1/3, ...). Is it geometric? If so, what is a and r? What is the 10th number? The 100th number?*
Figuring out the *k*th number in a given sequence is pretty good, but we can do better: we can figure out the *sum* of the first *k* numbers in any geometric
sequence in terms of only *a* and *r*. To do so, we'll use a beautiful trick of mathematical manipulation, one of the first of its kind that you're likely to run
across in a standard course.

A good first step is to name the think we're trying to find: let *S*_{k} stand for the sum of the first *k* numbers of the geometric sequence that starts
with *a* and has common ratio *r*. Explicitly then, we have:

*S*_{k} = *a* + *ar* + *ar*^{2} + ... + *ar*^{k-1}

Now the trick: take a look at what you get if you multiply this whole sum *S*_{k} by *r*:

*S*_{k} · *r* = (*a* + *ar* + *ar*^{2} + ... + *ar*^{k-1}) · *r* =
*ar* + *ar*^{2} + *ar*^{3} + ... + *ar*^{k}

Notice the overlap between the sum *S*_{k} and the sum *S*_{k} · *r*. We can take advantage of it by subtracting one from the other to
cancel the same terms:

*S*_{k} - *S*_{k} · *r* = (*a* + *ar* + *ar*^{2} + ... + *ar*^{k-1}) -
(*ar* + *ar*^{2} + *ar*^{3} + ... + *ar*^{k}) = *a* - *ar*^{k}

Since we originally set out to find a formula for *S*_{k}, we can now simply isolate *S*_{k} in the above equation:

*S*_{k} = (*a* - *ar*^{k})/(1 - *r*)

**Exercise 3:** *When does the reasoning above go wrong? (Hint: look at **r*). What special kind of geometric sequence does this problem correspond to?
Can you determine a formula for *S*_{k} that works in this special case?
Using this formula we can calculate, for example, the sum of the first 10 numbers in the sequence (50, 25, 12.5, ...) that we got out of Zeno's paradox:

*S*_{10} = (50 - 50 · (1/2)^{10})/(1-1/2) = 99.90234375

Whereas before we calculated the length of the 10th leg of the 100 meter dash, here we have calculated the total distance covered from the start of the
race to the end of the 10th leg. So after completing the first 10 sections of the (infinitely many sections of the) run, you will have gone almost the
whole distance: more than 99.9 meters!

**Exercise 4:** *What is the sum of the first 10 numbers of the sequence given in Exercise 2? The first 100?*
Since each leg of the 100 meter dash is exactly half the remaining distance to the finish line, it makes sense that the more legs we add up, the closer we'll get
to the full 100 meters. So we would expect *S*_{1000}, say, to be bigger than *S*_{10}, and therefore closer to 100, but not quite *equal*
to 100. Pushing this reasoning a step farther, in some sense the sum of *all* the numbers in the sequence must be *equal to* 100.

Here we have found a point of contact between the finite and the infinite: the sum of infinitely many numbers adding up to something finite.
In the right context it seems to make perfect sense: if you split up 100 meters into infinitely many shorter pieces, then of course the sum of the
lengths of all the pieces should be equal to the total length of 100.

But how can we make mathematical sense of the idea of adding infinitely many numbers together? In some cases, it turns out, you really can't, but with the right
restrictions on what you're adding up, things work out better.

We've already observed that the sequence motivated by Zeno's paradox is a geometric sequence, so let's restrict our attention to those. We know how to do finite sums:
we've calculated a formula for *S*_{k}in terms of *a* and *r*. What would be nice is a formula for '*S*_{∞}', the sum of
all the infinitely many numbers in a geometric sequence. To this end, we might look at the formula for *S*_{k} more closely and figure out what happens
to it as *k* gets very large.

The only place where *k* occurs in *S*_{k} is as an exponent: *r*^{k}. This doesn't help us much if *r* is a number like 2,
since 2^{k} gets bigger and bigger without bound as *k* is chosen to be bigger and bigger. This claim is often symbolized as:

2^{k} → ∞ as *k* → ∞,

and read "2^{k} goes to infinity as *k* goes to infinity".

**Exercise 5:** *Convince yourself of this.*
On the other hand, if *r* happens to be a number such that -1 < *r* < 1, the story is different. Remember that a positive number less than 1,
when squared, actually gets smaller. For example, (1/2)^{2} = 1/4. A similar fact holds for higher powers; in an earlier calculation,
for instance, we saw that (1/2)^{9} = 1/512. In fact, as the exponent *k* grows larger and larger, the power *r*^{k} gets closer and closer to 0:

*r*^{k} → 0 as *k* → ∞, provided that -1 < r < 1.

**Exercise 6:** *Convince yourself of this, too. Don't forget to consider the case where **r* is negative.
What's the point of all this? Well, if we consider only the case where -1 < *r* < 1 and examine the formula for *S*_{k}, we see that
the term *r*^{k} goes to 0 as *k* goes to infinity. We might therefore write:

*S*_{∞} = (a - a · 0)/(1 - *r*) = a/(1 - *r*)

The argument that led us to this formula was convincing (I hope!) but not rigorous. In fact, mathematical rigor in cases like these took a long time
to develop and can get quite technical. Though the details are accessible, I'd rather gloss over the finer points here so that we can get back to
settling Zeno's paradox and investigating related puzzles.

**Exercise 7:** *What is the sum of all the terms in the sequence given in Exercise 2?*