Welcome to the world of elementary number theory, which as we mentioned earlier, is not a euphemism for easy number theory. Instead, its an area of number theory that has its focus on elemental questions of numbers, most of whose subtle answers do not involve advanced mathematical techniques. Here, with the notions fresh in our minds of an arithmetic progression, a list of numbers generated by successive addition, we open our discussion on elemental number theory, by exploring the multiplicative cousin of arithmetic progressions.

These are known as geometric progressions, number lists generated by successive multiplication. A simple example arises by the mere act of doubling:

1, 2, 4, 8, 16, 32,...

These numbers grow at a dramatically fast rate, and possess enormous structure. We'll momentarily pause, later in this lecture, to consider how geometric progressions naturally appear in the world of music, as a means of producing an even tempered scale. This melodic excursion will involve notions that go back to the Pythagoreans and continue to confound piano tuners to this very day!

Next we'll turn to an extremely useful and important object in more advanced number theory, the sum of the terms of a geometric progression. Our exploration into the sums of these numbers will include some amusing ancient stories that hold important mathematical morals. We'll then extend this addition of terms and consider the endless sum of all terms of certain geometric progressions, and make such vexing ideas intuitive, by visualizing such sums geometrically. The endless sum of a geometric progression is known as a geometric series.

These series are fundamental in all branches of mathematics and science, especially as we'll see in future lectures, in number theory itself. We'll then close this discussion with a whimsical discussion of the utility of infinite geometric series in the lives of lucky game show contestants, the happy fantasy of winning a large cash prize, and the unpleasant reality of paying taxes on that new found bounty.

We'll lets begin by recalling that an arithmetic progression is a list of numbers, with the property that to get from any number to the next, we need only add a fixed value. As we'll discover as our course unfolds, these arithmetic progressions, while simple in structure, play an important role in our number theory story. Perhaps even more important however, are the corresponding progressions in which the addition is replaced by multiplication. These progressions are called geometric progressions.

To generate them, we must be given the first number, and then the constant multiple, known as the ratio, which generates the successive numbers on the list. For example, if we start with 1 and are given a ratio of 2, then our geometric progression starts with 1, and then continually multiplying our answer by 2, to get the next number:

1, 2, 4, 8, 16, 32, 64,...and so forth

It's easy to see that a general term in this geometric progression is given by 2ⁿ for some natural number n. The constant multiple, in the previous example being 2, is called the ratio because the ratio of any two consecutive terms, the larger to the smaller, is always equal to that constant ratio. For example, notice that if we take a look at 32 and 16 in out list, which are adjacent. If we take 32 and divide it by 16, so 32/16, we get that constant ratio 2. Hence that constant is called the ratio.

In general if we start with 1 and are given a ratio of say r, where r is just some number, then we could generate the geometric progression:

1, r, r², r³,...and so on

You keep multiplying the previous answer by an extra factor of r.

Well these examples show us that a general term in a geometric progression that starts with 1, is of the form rⁿ, for some whole number n. Since the varying quantity is the exponent n, if r>1, we say that rⁿ grows exponentially, a very dramatic growth.

If r is a small number, bigger than 0 but smaller than 1, so that 0<r<1, we say that rⁿ decays exponentially, because it shrinks down faster and faster. For example, if we start with 1 and consider the ratio r=1/2, then we have a geometric progression that decays exponentially. We have:

1, 1/2, 1/4, 1/8, 1/16, 1/32, ...and so on

Notice those terms are getting smaller and smaller, so it would be exponential decay in this case.

Well lets take a moment to consider exponential progressions in music and ratios of pitches. A musical interval is an octave if the two pitches have frequencies in a ratio of 2:1. An interval is a perfect fifth if the ratio of the frequencies of the two pitches is 3:2.

So for example, in modern western music, the pitch A (above middle C) has a frequency of 440 Hertz, which is usually written as 440 Hz. Thus the pitch A, one octave higher, has a frequency of 440 Hz x 2, or 880 Hz. And the pitch E, one fifth higher than A 440 Hz, has a frequency of 440 Hz x 3/2 = 660 Hz.

In western music, the chromatic scale begins at one pitch, say A, and progresses up in what are called half steps, until it ends with a note that is one octave above the starting pitch. The pitches are derived from a progression of perfect fifths, starting with the first pitch. Well a progression of perfect fifths, is nothing more than a geometric progression with the ratio r = 3/2. So if we start at A 440 Hz, we would have:

440, then 440 x 3/2, then 440 x (3/2)², then 440 x (3/2)³, ...and so on,

So in fact, the number we get would be:

440, 660, 990, 1485, ...and so forth.

Now of course, these pitches are so high, that only our pets would actually hear them, so we really wouldn't be able to appreciate the music. So in order to keep the notes within the 440 - 880 Hz range, we divide the frequencies by 2, in order to lower the pitches, so that they fall into the correct octave. Well this process actually requires us to modify our attractive geometric progression, sadly, but then happily we could actually hear the pitches that are generated.

So why do we end up with a 12 note chromatic scale? Well the answer to this, which we'll discover for ourselves later in the course, involves irrational numbers, which we haven't even talked about. So we'll leave this as a musical and mathematical cliff hanger, for now. But we will return to the question of why 12?

Returning now to the geometric progressions, that are the focus of this lecture, we note that it would be extremely useful to find the sum of the first few terms in a geometric progression, just as we did with arithmetic progressions. Now if we can consider the geometric progression:

1, 3, 9, 27, 81,...and so forth.

Here the common ratio is 3, since we multiply by 3 each time, then the first five successive sums would be:

1, 4, 13, 40, 121,...

And where do these numbers come from? Well we just add up the terms in the geometric progression. So for example:

1+3=4
1+3+9=13
1+3+9+27=40
etc.

Now a pattern is not immediately apparent. You can see that we're moving into a more sophisticated world of number, because now the pattern doesn't just pop out. This is now going to require some thinking. So to build some intuition, we'll explore a particular example with some great care. So lets actually consider the example we just looked at where we have a constant multiple or ratio of 3. Lets let s be the sum of the first 5 terms:

S = 1 + 3 + 3² + 3³ + 3^4

So we have all those numbers, which by the way, equals 121. Lets just keep that in that back of our heads.

Well here's the wonderful trick that's going to simplify this object. Let's now multiply both sides of this equation by 3.

3(S=1+3+3²+3³+3^4)

When we multiply the left hand side by 3, we're left with 3 S's. When we multiply the right hand side by 3, we see that every single term in that sum, gets hit with another factor of 3. If you notice what happens, the one, when multiplied by a three, equals three. The 3, when multiplied by a 3, equals 3². It's kind of like those late night programs where if the new guest comes on, the old guests shift down. We just shift everyone down one, so we see three plus three squared, plus three cubed, plus three to the 4th, and that last term which originally was 3^4, when we multiply it by and extra factor of 3, becomes 3^5:

3S = 3 + 3² + 3³ + 3^4 + 3^5

Well when we line these things up, and subtract the two equations, on the left side we see three S's, and we're subtracting one S, so that's three minus one, times S.

3S = 3 + 3² + 3³ + 3^4 + 3^5
-S = 1 + 3 + 3² + 3³ + 3^4)
_____________________________
(3-1)S =

On the right hand side, notice that all the terms in the middle there, in the interior, all align perfectly and actually add to give zero, like 3-3, 3²-3², 3³-3³, 3^4-3^4. All we're left with, on the very top, is that 3^5, that dangling term way off the right. Then on the bottom, we're subtracting that first one, so we see:

3S = 3 + 3² + 3³ + 3^4 + 3^5
-S = 1 + 3 + 3² + 3³ + 3^4)
_____________________________
(3-1)S = -1 + 3^5

So we divide by (3-1) and can find that:

S = (3^5 - 1)/(3-1) = (243-1)/2 = 121

This sum is the one we expected So we find something interesting here. What do we find? The value of this particular sum, is three raised to a power, where the power is one higher than the highest exponent appearing in the sum of terms, and then we subtract off one, and finally divide by three minus one, the ratio minus one.

In fact, this is the pattern we've been searching for. We can check to see if this pattern holds for other sums. For example, lets apply the analogous pattern with:

1 +3 + 3² + 3³

Well we would conjecture that the sum would equal:

(3^4 - 1)/(3-1) = (81 - 1)/2 = 40

which is exactly what we saw earlier.

Well we can now derive a formula for the more general sum:

1 + 3 + 3² + 3³ +...+ 3ⁿ

where n is some unknown natural number. Now we'll again call this sum S, for convenience. We'll just follow the exact same trick as before. One great thing about mathematicians, is that once we have a great idea, we try to recycle it again and again. So if we multiply this entire equation by 3, we can align most of those interior terms of S, with most of the terms of 3S, and then we can subtract. So we have:

3S = 3 + 3² + 3³ + 3ⁿ + 3ⁿ*¹
-S = 1 + 3 + 3² + 3³ + 3ⁿ
_________________________________

(3-1)S = -1 + 3ⁿ*¹

(3-1)S = -1 + 3ⁿ*¹

Again solving for S, we see that:

S = (3ⁿ*¹ - 1)/(3-1) = (3ⁿ*¹ - 1)/2

Well we can now consider the corresponding sum for any ratio, r. So lets consider:

1 + r + r² + r³ +...+ rⁿ

Again, we'll call this sum, S. If we multiply S by r, which is now the ratio (it used to be 3), we can align most of the terms in S, with most of the terms in rS:


rS = r + r² + r³ +...+ rⁿ + rⁿ*¹
-S = 1 + r + r² + r³ +...+ rⁿ
__________________________________


Look at the economy of ideas, so that we're just taking this one idea, and then looking at variations on a theme, with the variations being the generalization. So we have:

rS = r + r² + r³ +...+ rⁿ + rⁿ*¹
-S = 1 + r + r² + r³ +...+ rⁿ
__________________________________

(r-1)S = -1 + rⁿ*¹

solving again for S, we see:

S = (rⁿ*¹ - 1)/(r-1)

So we see the general manifestation of the formulas we saw with the r = 3. Now Euclid in fact, derived this formula, around 300 BCE. So this formula goes back to antiquity.

Now we want to take a moment to share the legend of the most modest mathematician. Here we'll see another example of the sum of a geometric progression. So this is a very old tale that Edward really enjoys.

Quite a while ago, a king wished to reward a royal mathematician, and asked him what he desired. The mathematician, who by the way appeared both modest and humble, replied that if just one grain of rice was placed on a square of an ordinary 8 by 8 chess board, and then two grains of rice in the next square, and so forth, doubling the previous amount of rice, until the last square on the chessboard was reached, then he would be totally content with the total sum of all the grains of rice.

Well the king laughed, and immediately granted this seemingly small request. However the king quickly stopped laughing, for the number of grains of rice owed to the mathematician, equaled the sum of the terms from a geometric progression. Now lets that a look at this in action for a second.

Here we have a chessboard, and so the mathematician asked for one grain of rice in the first spot, and now we're considering the geometric progression where we double each time. The next one would be two grains of rice, so there we have two. If we double again, we see four grains of rice. The next would consist of eight grains, and you can see that we then have sixteen, and so forth. Now you see the pattern.

OK, now the mathematician wants the sum of all the grains of rice. So we're actually adding up a geometric progression. We add one plus two plus two squared, plus two cubed, plus two to the fourth, and now lets just think about it. What's the very last square? Two to what power?

Well we start with one, and then we have two to the first power, then two squared in the third sport, we have two to the third in the fourth spot, and so on. So what do we see? We see in the last spot, in the 64th spot, we're going to have two to the 63rd power. Because notice that we started with a one, and then went to two to the first, two to the second in the third spot, two to the third power in the fourth spot,and so forth.

So in the 64th spot, it'll be at the power 63. So we're adding:

1 + 2 + 2² + 2³ + 2^4 +...+ 2^63

So this is the geometric progression where we have r=2, and we're going to sum all the terms up, up to n=63. So our formula tells us the answer:

(2^64 - 1)/(2-1) = 18,446,744,073,709,551,615

This twenty digit number is a lot of grains of rice. How can we make sense of this extremely large amount of grains of rice? Given that a grain of rice weighs approximately 0.033 grams, this pile of rice would weigh more than 671 billion tons! To place this tonnage in perspective, today the world produces approximately a half a billion tons of rice each year, so this would take an awful long time just to grow, well over 1200 years.

Well needless to say, the king was faced with two choices. Either give up his entire kingdom to the mathematician to begin to pay off this enormous debt, or simply have the mathematician executed. Guess who had the last laugh?!

Anyway, this is an important moral, both about how quickly geometric progressions accumulate when you add them up, and also about how mathematicians shouldn't be so greedy, especially if they come across as being quite modest!

Well finally, we consider summing up infinitely many numbers from a geometric progression. So first we must ask, when does an infinite sum of terms from a geometric progression even make sense? Lets begin recalling that for any value of r that's not equal to 1, the formula for the sum of:

1 + r + r² + r³ +...+ rⁿ = (rⁿ*¹ - 1)/(r-1)

That was the formula for the sum of the terms in the geometric progression we found. Well we now suppose that the ratio r, is a small number. Let's say its a positive number, less than 1. So lets think about it. As n gets larger and larger, rⁿ is going to be getting smaller and smaller. In fact, it approaches zero.

For example, if we let r = 1/2, then lets look at the geometric progression:

1, 1/2, 1/4, 1/8, 1/16, 1/32, ...and so on

You can see that as the denominator gets larger, the actual term, the fraction, is smaller and heading to zero. In this case we can actually consider the infinite sum of all the numbers in this geometric progression. This infinite sum is known as a geometric series, and is extremely important in out study of number theory. So we'll come back to this again and again.

A geometric series is an infinite sum of the form

1 + r + r² + r³ +... and so on endlessly.

Does such an endless sum have a numerical value? As always, we search for a pattern, through an example. Lets consider the geometric series:

1 + 1/2 + (1/2)² + (1/2)³ + (1/2)^4 + (1/2)^5 + ...

If we view these individual terms as representing lengths of a line segment, each one representing a shorter and shorter line segment, then we can see geometrically that this infinite series equals two. We want to demonstrate this right now. We see a rod that represents little piece of a number line. Think of the part on the left as being zero, and the middle as one, and finally the right side as two.

If we look at the very first term in the sum, we actually see that it's 1, so we consider the length of this line segment as 1 with a silver pointer. It's sort of like an old extendable radio antenna. It goes from 2 to 1.

Now we add the next term in our series which is one half, which brings the pointer halfway from where we currently are, to the point on the line which represents 0.

Then we add 1/2, which is again halfway from where we currently are. Then we add an eighth, again halfway. Next a sixteenth, halfway. Then a thirtysecond, halfway. A sixtyfourth, so that we keep taking half and half and half.

If we do that forever, we will in fact fill up the entire line segment, so that we see this infinite series actually geometrically seems to fill up this line, and has length 2. So the series has a numerical value of 2.

Now lets consider:

1 + 1/2 + (1/2)² + (1/2)³ + (1/2)^4 +...+ (1/2)^n

Well we have the formula for that finite sum. It's:

((1/2)ⁿ*¹ - 1)/((1/2) - 1)

Recall that (1/2)ⁿ*¹ is approaching zero, as the n gets larger and larger. So thus, this formula is heading toward:

(0 - 1)/((1/2) -1) = -1/(-1/2) = 2

This agrees with our geometric analysis from a moment ago.

more generally, for any ratio 0<r<1, we recall that:

1 + r + r² + r³ +...+ rⁿ = (rⁿ*¹ - 1)/(r-1)

The rⁿ*¹ is approaching zero as n gets larger and larger. Remember that we're assuming the r is a positive number less than 1 in this case, so higher powers will make the thing actually shrink. Thus we see that the infinite series:

1 + r + r² + r³ +...and so forth endlessly,

will actually equal:

1/(1-r)

This is just as we saw for the example of the one halves.

We can apply this formula to find the value, say, of:

1 + (1/5) + (1/5)² + (1/5)³ +...

Here we see the ratio equals the value of 1/5, so what does our ratio tell us that this geometric series sums to?

1/(1-1/5) = 1/(4/5) = 5/4

So that infinite series, sums to a number, which is 5/4.

This formula for an infinite geometric series is an important identity which we'll utilize as we move deeper and deeper into the world of number theory. This identity for the sum of an infinite geometric progression, these geometric series', we'll come back to again and again.

We close with a prize winning application. Suppose that you win a $1 million prize on a television game show. Congratulations! You first believe that you have $1 million to enjoy, which sounds great. However, uncle Sam has other plans for you. He will take 1/3 of your bounty, in taxes.

Yet suppose that the television network wants to generate so much hype, that it offers to actually pay the tax for you, so you'll take home the full $1 million. They say they will give you 1 + 1/3 million, soyou can pay off that 1/3 to the government.

However you still don't take home $1 million. Do you see why? You now have to pay 1/3 tax on the extra 1/3 million they gave you! That's an extra 1/9 of $1 million in tax to pay additionally. If they offer to pay the extra 1/9 of a million, which sounds good, you then still have an additional amount which will be taxed as well.

So how much must they offer you, so that you really take home $1 million after taxes? The answer is the infinite geometric series:

1 + 1/3 + (1/3)² + (1/3)³ + ...and so on, endlessly.

What does our formula tell us? Here we see the common ratio r is 1/3, so our series sums to:

1/(1-(1/3)) = 1/(2/3) = 3/2

So 3/2 million dollars is what the game show has to provide. Actually, we can see that the tax on this amount is, well we have 3/2 million, multiplied by 1/3, to get 1/2 million in taxes to pay. So if we deduct this amount from the 3/2 million that we have, which is one and a half million minus the half million in tax, so that we see we are left with $1 million after taxes.

The power of a geometric series, is one that will be with us throughout our course. The fact there is such an elegant formula that we ourselves can derive, for that infinite sum of ever shrinking terms in a geometric progression, is certainly a work of beauty. It's certainly worth $1 million!