Geometric Series

S_n(x) = (xⁿ⁺¹ - 1)/(x-1) .

The first derivation shows how a general formula can be discovered by carefully examining what we already know. The second derivation shows how a result may be discovered serendipitously when examining some other problem. My intention is to present the proofs in such a way that the concept of geometric series and the formula for it will stay with the student.

After the proofs there is a section on infinite geometeric series followed by examples of geometric series.

The Geometric Series Everybody Knows

If I asked you to find 99999999999999999999999 + 1, you would have no trouble writing the answer. Just write a one followed by a zero for each one of the twenty-three nines:

 99999999999999999999999 
+______________________1
100000000000000000000000. (Eq 1)

Below I show the first few steps of computation. Step 0 is the start of the problem where no distance has been traveled and the remaining distance is 1.

At each step the remainder is 1/3 of the remainder for the previous step. Since the initial remainder is 1, after n steps the remainder is (1/3)ⁿ. The answer to the problem therefore is that the distance traveled after n steps is (1 - remainder) or 1 - (1/3)ⁿ.

Let us look now at the series formed by the individual increments of distance. After step one we have:
2/3 + 1/3 = 1.

On the second step the remainder of 1/3 is divided into a distance traveled and a remainder, so we have
2/3 + 1/3*(2/3 + 1/3) = 1, or
2/3 + 2/3*1/3 + (1/3)² = 1.

On the third step the remainder of (1/3)² is divided into a distance traveled plus a remainder, giving
2/3 + 2/3*1/3 + (1/3)² *(2/3 + 1/3) =1, or
2/3 + 2/3*1/3 + 2/3*(1/3)² + (1/3)³=1

Thus after n+1 steps we have:
2/3 + 2/3*1/3 + 2/3*(1/3)² + ...+ 2/3*(1/3)ⁿ + (1/3)ⁿ⁺¹=1.

This can be written as 2/3*S_n(1/3) + (1/3)ⁿ⁺¹= 1 or
S_n(1/3)=(1 - (1/3)ⁿ⁺¹)/(1 - 1/3).

This is the equation for S_n(x) for x = 1/3 with the numerator and denominator multiplied by -1. In the above derivation 1/3 and 2/3 could be replaced by x and (1 - x) for any x between 0 and 1.

What about values of x that are not between 0 and 1? We could forget about traveling and use the above procedure to get the following purely algeraic derviation.
(1-x) + x = 1.
(1-x) + x*[(1-x)+x] = 1, (1-x) + (1-x)*x + x² =1.
(1-x) + (1-x)*x + x²*[(1-x)+x] =1, (1-x) + (1-x)*x + (1-x)*x² + x³ = 1.

We could continue in this way to show that (1-x)*S_n (x) + xⁿ⁺¹ = 1, from which the general equation for S_n follows.
This traveler problem is an example of a frequently used mathematical model. For further details see Exponential Growth and Decay.


Infinite Geometric Series

The previous section provides a way of picturing infinite geometric series. The traveling problem at step n can be written as:
2/3*S_n(1/3) + (1/3)ⁿ⁺¹ = 1.
The term (1/3)ⁿ⁺¹ keeps getting smaller and will stay arbitrarily close to zero once we pass a sufficiently large value of n. We can then speak of S_inf(1/3) as the distance traveled after an infinite number of steps. We have
2/3*S_inf(1/3) = 1, or S_inf(1/3) = 1/(2/3) = 3/2 = 1.5.
1 + (1/3) + (1/3)² + (1/3)³ + (1/3)⁴ + ... = 1.5.

Similarly, for x between 0 and 1,
S_inf(x) = 1/(1-x).

Now consider the following problem of an indecisive traveler. This traveler starts out by traveling a mile. The traveler then backtracks for 1/2 a mile and then turns around and travels 1/4 mile and continues this way, each time reversing direction and traveling 1/2 the previous distance. Where will this traveler end up?

The series for this problem is:
1 - 1/2 + 1/4 -1/8 + 1/16 +...

This is the geometric series for -1/2, S_inf(-1/2):
1 + (-1/2) + (-1/2)² + (-1/2)³ + (-1/2)⁴ + ... .
For negative fractions, just as for positive ones, the term xⁿ goes to zero for large n.

Therefore we can compute S_inf(-1/2) as:
S_inf(-1/2) = 1/(1 - (-1/2)) = 1/(3/2) = 2/3.

The formula S_inf(x) = 1/(1 - x) applies to all numbers x between -1 and 1.

Although the algebra for geometric series of negative numbers is the same as that for positive numbers I include it as a special case because all of us, even full-fledged mathematicians, are more reluctant to use negative numbers than positive ones.

Repeating Decimals

Most people are told some time before they get out of high school that a repeating decimal can be expressed as a fraction. I doubt that many of these people know that the repeating part of a repeating decimal is a geometric series.

By way of review, a repeating decimal is a number with the form:
a.bcccccc...,
where a, b and c are strings of digits and the c part repeats forever. For example 12.3456565656... .

We can express this last number as 12.34 + .00565656... .
12.34 = 12 + 34/100 can obviously be expressed as a fraction. If we can show that .00565656... is a fraction then we are done.

.00565656... = .0056 * (1 + .01 + .0001 + ...) =
.0056 * (1 + (1/100) + (1/100)² + (1/100)³ +...) =
(56/10000 ) * (1/(1 - 1/100)) = (56/10000) * (100/99) =
56/ 9900.

An easy but instructive exercise is to devise a method of constructing an infinite non-repeating decimal using only the digits 0 and 1.

Factorization

The equation for S_n(X) provides a way of factoring the expression Xⁿ - 1.

Xⁿ - 1 = (X - 1) * S_n-1(X) = (X - 1) * (1 + X + X² + ... + X^n-1). In expanding this expression all the terms cancel except for the terms for Xⁿ and -1. The easiest way to how this works is to try expanding a simple example such as (X - 1) * (1 + X + X² + X³).

To generalize from Xⁿ - 1 to Xⁿ - Yⁿ, consider the expression for:
(1 - (3/5)ⁿ) = (1 - 3/5) * (1 + (3/5) + (3/5)² + ... + (3/5)^n-1)

From the expression for Xⁿ - Yⁿ it is easy to get the factorization for Xⁿ + Yⁿ when n is an odd number by observing that Xⁿ + Yⁿ = Xⁿ - (-Y)ⁿ when n is odd. Now it is only necessary to substitute (-Y) for Y in the above factorization. I leave the details as an exercise.

As a second exercise, derive the formula for Xⁿ - Yⁿ using a variation of the traveler approach for geometric series. In place of one mile have a starting distance of 5ⁿ. Have the traveler go 2/5 of the remaining distance each time. Create a chart like the one above and fill in two or three columns. The increment will be 2/5 of the previous remainder and the new remainder will be 3/5 of the previous one. Show that the k^th increment is 2*5^(n-k)*3^(k-1) and the new remainder is 3^k. What will the remainder be after n steps?

Suppose it takes three hours to download a video tape with a one hour playing time. You would like to be able to start watching the tape before it completely downloads in such a way that there are no interruptions. What fraction has to be downloaded before you can do this? Once you see how geometric series relates to this problem, the solution is simple. See if you can figure it out before reading any further.

Let x be the number of minutes of playing time that is downloaded before you start watching. After x minutes of viewing, an additional x/3 minutes are available. And after watching the x/3 minutes there will be another x/9 minutes and so on. It follows that the total amount of time that you will be able to view the tape without interruption is
x/(1 - 1/3).
For this to cover the entire tape we must have
x/(1 - 1/3) = 60 mimutes.
So x = (1 - 1/3)60 = 40 minutes.
You will be able to watch the tape without interruption after 2/3 of it has been downloaded.

This result can also derived without use of geometric series. During the hour that the video is watched, there can be a download of 1/3 hour. Therefore, before watching the video, there must already have been a download of 2/3 hour, in agreement with the above derivation. It now remains to show that there will always be at least as much downloaded as has been watched. If t is the amount of time in hours spent watching then 2/3 + t/3 is the amount downloaded. We want to show that the second expression is always at least equal to t. (2/3 + t/3) - t = 2/3(1 - t), which is greater than 0 for t > 1 hour and equal to zero for t = 1 hour.

The British mathematician John Conway used a geometric series to solve a recreational math problem that he created, or more accurately, to show that no solution is possible.

For those who have never worked with a peg solitaire puzzle, these puzzles have an arrangement of holes into which pegs are initially inserted. The puzzle is then solved by a sequence of jumps. A peg jumps over another one, similar to jumps in checkers, and the pegged that was jumped over is removed. The objective is usually to achieve some final configuration.

In the Solitaire Army problem, the holes are arranged in an infinite rectangular grid. A horizontal line is placed on the grid between two adjacent horizontal rows. The idea of the problem is to place an initial arrangement of pegs below the horizontal line and then to execute a sequence of jumps that will place a peg a specified number of rows above the horizontal line. Although it may seem that it is possible to advance any arbitrary distance, it turns out that the maximum amount is four. The reader may want to try this out .

The target hole and the ones below it are shown in color. To find the sum of the holes below the line we will first find the sum of the values in the row below the line by adding the two geometric series. We will then use another geometric series to add the rows.

We will make use of two properties of p easily derived from the defining relationship p² + p =1. The first, which follows immediately by subtracting p from both sides is:

To get the second equation, factor the left side of p² + p =1 to get, p*(1+p)=1, and then divide both sides by 1+p to get:

First add the p⁵ and everything to the right of it to get:

p⁵ + p⁶ + p⁷ + ... = p⁵ * (1 + p + p² + p³ + ...) = p⁵ * S_inf(p) = p⁵ / (1 - p) = p⁵ / p² = p³, using the first of the two above equations.

Similarly, the p⁶ term and all the terms to the left give p⁶*S_inf(p)=p⁴.

The value of the first row is p⁴ + p³ = p³*(1 + p) = p³ * (1/p) = p², using the second of the above two equations.

Since the value of the first row is p² and each row is p times the previous one, the sum of the rows is p² + p³ + p⁴ + ... = p²*S_inf(p) = p²/(1 - p) = p²* (1/p²) =1. Since the sum of all the holes below the line is 1, any position with only finite number of pegs must have value less than 1 and therefore the target position, with value 1, is unreachable.

(x - 1) * S_n(x) = x*S_n(x) - S_n(x) =

x*(1 + x + x² + x³ + ... + xⁿ) - (1 + x + x² + x³ + ... + xⁿ) =

     (x + x2 + x3 + ... + xn +  xn+1)
-(1 + x + x2 + x3 + ... + xn) =

 xn+1 - 1.

(x - 1) * S_n(x) = xⁿ⁺¹ - 1.

S_n(x) = (xⁿ⁺¹ - 1) / (x - 1).

I have criticized the standard proof for not being sufficiently intuitive. I should point out, however, that the general technique employed in the proof can be used to solve other problems. As an example I offer the following exercise.

Consider the series T_n(x) = 1 + 2*x + 3*x² + 4*x³ + ... + (n+1)*xⁿ. Using the above proof as a guide, show that (x-1)*T_n(x) = (n+1)*xⁿ⁺¹ - S_n(x), where S_n(x) is a geometric series. Now substitute the formula for geometric series to show that:
T_n(x) = ((n+1)*xⁿ⁺² - (n+2)*xⁿ⁺¹ + 1) / (x - 1)².

Addendum

I thought of this very intuitive way of looking at geometric series while watching a tennis tournament on television.

In order for all the winners of a round to be able to play in the next round there must be an even number of players in each round, and in order for this to happen the initial number of players must be a power of two, say 2ⁿ⁺¹ . There will then be 2ⁿ games in the first round, 2^n-1 games in the next round and so on until the one game in the final round.

If the tournament starts with 2⁶ = 64 players then:
Total number of games = 32 + 16 + 8 + 4 + 2 + 1 =
2⁵ + 2⁴ + 2³ + 2² + 2 + 1

We can also get the total number of games by reasoning as follows. Since there are initially 64 players and only 1 player remains at the end, 63 players must be eliminated and since 1 player is eliminated per game, the total number of games must be 63.
Total number of games = 64 -1 = 63.

32 + 16 + 8 + 4 + 2 + 1 = 63 and, in general,
2ⁿ + 2^n-1 + ... + 1 = 2ⁿ⁺¹ - 1, which is the formula for geometric series S_n(x) for x=2.

Let us generalize this to a tournament for a game with x players. You can think of a board game like Monopoly or Parchesi. Only the winners from each round go on to the next round.

At the start of the tournament there will be xⁿ⁺¹ players and the first round will contain xⁿ games, the next round will contain x^n-1 games and the total number of games is:

xⁿ + x^n-1 +x^n-2 +... + x + 1.

Now let us derive the number of games by counting the number of people eliminated from the tournament. The tournament starts with xⁿ⁺¹ players and ends with 1 grand champion, so there must be a total of xⁿ⁺¹ - 1 people eliminated. Since there are x-1 people eliminated per game, the total number of games must be (xⁿ⁺¹ - 1)/(x-1). Equating the two expressions for the number of games gives the formula for geometric series.

Turning this into a proof is very similar to the traveler proof. Instead of starting with a distance of 1, we start with xⁿ⁺¹ players. In the first round the xⁿ⁺¹ people play xⁿ games, each with 1 winner and (x-1) losers, or algebraically:

xⁿ⁺¹ = xⁿ*((x-1)+1) = (x-1)*xⁿ + xⁿ

In the next round, the xⁿ winners play in x^n-1 games, or:

xⁿ⁺¹ = (x-1)*xⁿ + x^n-1*((x-1)+1) =
(x-1)*xⁿ + (x-1)*x^n-1 + x^n-2.

We continue in this way until the final game of x players, from which x-1 are eliminated and 1 remains:

xⁿ⁺¹ = (x-1)*xⁿ + (x-1)*x^n-1 + x^n-2 + ... + (x-1) +1.

Subtracting 1 from both sides and dividing by x-1 gives the formula.

Finally, note that by concentrating on the number of people eliminated, it is possible to determine the number of games even if the starting number of players is not xⁿ⁺¹. For example, if there are 3 people per game and the initial number is 13, the total eliminated is 13 - 1 = 12 and the number eliminated per game is 3 - 1 = 2, so the total number of games is 12/2 = 6. In the first round there would be 4 games of 3 with one person getting a bye. In the second round there would be 5 players remaining for 1 game of three with two getting byes. In the third round there would be 3 people remaining for 1 final game.

HOME