A geometric series has the form Sn(x) = 1 + x + x2 + ... + xn . The equation for the geometric series is:
Sn(x) = (xn+1 - 1)/(x-1) .
Geometric series are frequently used in mathematics. They also provide a good introduction to infinite series. I will present two different intuitive derivations of the geometric series. Neither of these proofs is as slick (or elegant, as mathematicians say) as the standard proof. What the standard proof has in brevity it lacks in immediacy. I will present it at the end of this section so that you can judge for yourself.
The first derivation shows how a
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:
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.
1/3 * 1/3 = (1/3)2
1/3 * (1/3)2=(1/3)3
2/3 * 1/3
2/3 * (1/3)2
2/3 + 2/3 * 1/3
2/3 + 2/3*1/3 + 2/3*(1/3)2
2/3 + 1/3 = 1
2/3 + 2/3 * 1/3 + (1/3)2 = 1
2/3 + 2/3*1/3 + 2/3*(1/3)2 + (1/3)3= 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)n. The answer to the problem therefore is that the distance traveled after n steps is (1 - remainder) or 1 - (1/3)n.
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)2 = 1.
On the third step the remainder
of (1/3)2 is
divided into a distance traveled plus a remainder, giving
2/3 + 2/3*1/3 + (1/3)2 *(2/3 + 1/3) =1, or
2/3 + 2/3*1/3 + 2/3*(1/3)2 + (1/3)3=1
Thus after n+1 steps we have:
2/3 + 2/3*1/3 + 2/3*(1/3)2 + ...+ 2/3*(1/3)n + (1/3)n+1=1.
This can be written as 2/3*Sn(1/3) + (1/3)n+1= 1 or
Sn(1/3)=(1 - (1/3)n+1)/(1 - 1/3).
This is the equation for Sn(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 + x2 =1.
(1-x) + (1-x)*x + x2*[(1-x)+x] =1, (1-x) + (1-x)*x + (1-x)*x2 + x3 = 1.
We could continue in this way to show that (1-x)*Sn (x) + xn+1 = 1, from which the general equation for Sn 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*Sn(1/3) + (1/3)n+1 = 1.
The term (1/3)n+1 keeps getting smaller and will stay arbitrarily close to zero once we pass a sufficiently large value of n. We can then speak of Sinf(1/3) as the distance traveled after an infinite number of steps. We have
2/3*Sinf(1/3) = 1, or Sinf(1/3) = 1/(2/3) = 3/2 = 1.5.
1 + (1/3) + (1/3)2 + (1/3)3 + (1/3)4 + ... = 1.5.
Similarly, for x between 0 and 1,
Sinf(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, Sinf(-1/2):
1 + (-1/2) + (-1/2)2 + (-1/2)3 + (-1/2)4 + ... .
For negative fractions, just as for positive ones, the term xn goes to zero for large n.
Therefore we can compute Sinf(-1/2) as:
Sinf(-1/2) = 1/(1 - (-1/2)) = 1/(3/2) = 2/3.
The formula Sinf(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.
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:
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)2 + (1/100)3 +...) =
(56/10000 ) * (1/(1 - 1/100)) = (56/10000) * (100/99) =
An easy but instructive exercise is to devise a method of constructing an infinite non-repeating decimal using only the digits 0 and 1.
The equation for Sn(X) provides a way of factoring the expression Xn - 1.
Xn - 1 = (X - 1) * Sn-1(X) = (X - 1) * (1 + X + X2 + ... + Xn-1). In expanding this expression all the terms cancel except for the terms for Xn and -1. The easiest way to how this works is to try expanding a simple example such as (X - 1) * (1 + X + X2 + X3).
To generalize from Xn
- 1 to Xn
consider the expression for:
(1 - (3/5)n) = (1 - 3/5) * (1 + (3/5) + (3/5)2 + ... + (3/5)n-1)
From the expression for Xn - Yn it is easy to get the factorization for Xn + Yn when n is an odd number by observing that Xn + Yn = Xn - (-Y)n 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 Xn - Yn using a variation of the traveler approach for geometric series. In place of one mile have a starting distance of 5n. 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 kth increment is 2*5(n-k)*3(k-1) and the new remainder is 3k. What will the remainder be after n steps?Geometric Series and Mortgage Payments
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 .
Each time that a jump is made the number of possibilities for the final position diminishes. We may think of the pegs as a resource which is depleted with each jump. To implement this idea we could assign a value to each position in such a way that after each jump the value of the new position is less than or equal to the previous one - the value of all positions that can be reached from an initial position will be less than or equal to the value of the initial position. Let us assign a value to a position by assigning a value to each hole and computing the value of a position as the sum of the values of the holes occupied by pegs. To prove that a certain hole above the horizontal line is unreachable it would be sufficient to show that the value of that hole is greater than the sum of all the holes below the line.
As should become clear, a geometric series is well suited for assigning values in such a way that each jump lowers or keeps same the value of a position. Obviously, it is only necessary to consider the values of the three holes involved in the jump. If these three holes have values of pn, pn+1 and pn+2 then a jump that goes from pn and pn+1 to pn+2 will have a lower value for p less than one, which must be the case since we are dealing with an infinite series. Going in the other direction, from pn+2 and pn+1 to pn, suppose we chose p so that:
pn+2 + pn+1 = pn.
In this case the value of the new position will be the same as that of the preceding one. Dividing both sides by pn we then have
p2 + p = 1,
which is a quadratic equation whose solution positive solution is (-1 + sqrt(5))/2 = 0.618. I will note only in passing that 1/p is a number known as the Golden Ratio, which shows up in numerous mathematical contexts. In what we will be doing here the value of p will not be used, only the defining equation p2 + p = 1.
Let us assign a value of 1 to a hole that is a distance of 5 above the line. This value of 1 is the initial value of a geometric series extending to the left and of another geometric series extending to the right. Going from one row to the one below it, each hole has a value equal to p times the value of the hole immediately above it. See the picture below.
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 p2 + p =1. The first, which follows immediately by subtracting p from both sides is:
1 - p = p2
To get the second equation, factor the left side of p2 + p =1 to get, p*(1+p)=1, and then divide both sides by p to get:
Finding the top row sum:
First add the p5 and everything to the right of it to get:
p5 + p6 + p7 + ... = p5 * (1 + p + p2 + p3 + ...) = p5 * Sinf(p) = p5 / (1 - p) = p5 / p2 = p3, using the first of the two above equations.
Similarly, the p6 term and all the terms to the left give p6*Sinf(p)=p4.
The value of the first row is p4 + p3 = p3*(1 + p) = p3 * (1/p) = p2, using the second of the above two equations.
Adding the rows:
Since the value of the first row is p2 and each row is p times the previous one, the sum of the rows is p2 + p3 + p4 + ... = p2*Sinf(p) = p2/(1 - p) = p2* (1/p2) =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.
Standard Proof of Geometric Series
(x - 1) * Sn(x) = x*Sn(x) - Sn(x) =
x*(1 + x + x2 + x3 + ... + xn) - (1 + x + x2 + x3 + ... + xn) =
(x + x2 + x3 + ... + xn + xn+1)
-(1 + x + x2 + x3 + ... + xn) =
xn+1 - 1.
(x - 1) * Sn(x) = xn+1 - 1.
Sn(x) = (xn+1 - 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 Tn(x)
= 1 + 2*x + 3*x2
+ ... + (n+1)*xn.
Using the above
proof as a guide, show that (x-1)*Tn(x)
is a geometric series.
Now substitute the formula for geometric series to show that:
Tn(x) = ((n+1)*xn+2 - (n+2)*xn+1 + 1) / (x - 1)2.
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 2n+1 . There will then be 2n games in the first round, 2n-1 games in the next round and so on until the one game in the final round.
If the tournament starts with 26
= 64 players then:
Total number of games = 32 + 16 + 8 + 4 + 2 + 1 =
25 + 24 + 23 + 22 + 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
Total number of games = 64 -1 = 63.
32 + 16 + 8 + 4 + 2 + 1 = 63
and, in general,
2n + 2n-1 + ... + 1 = 2n+1 - 1, which is the formula for geometric series Sn(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 xn+1 players and the first round will contain xn games, the next round will contain xn-1 games and the total number of games is:
xn + xn-1 +xn-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 xn+1 players and ends with 1 grand champion, so there must be a total of xn+1 - 1 people eliminated. Since there are x-1 people eliminated per game, the total number of games must be (xn+1 - 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 xn+1 players. In the first round the xn+1 people play xn games, each with 1 winner and (x-1) losers, or algebraically:
xn+1 = xn*((x-1)+1) = (x-1)*xn + xn
In the next round, the xn winners play in xn-1 games, or:
(x-1)*xn + (x-1)*xn-1 + xn-2.
We continue in this way until the final game of x players, from which x-1 are eliminated and 1 remains:
+ (x-1)*xn-1 +
+ ... + (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 xn+1. 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.