Katy's Theorem

In the middle of April 2006 I found on the
Internet an utterly delightful gem of a work that gives me another opportunity
to look at the contrast between empirical-inductive reasoning and
axiomatic-deductive reasoning in mathematics. On the website
__www.shout.net,__
in the item titled "Discoveries about INFINITE SERIES",
a high-school sophomore identified only as Katy describes how she, under the
guidance of her math teacher, Mr. Cohen, induced a charming theorem involving
the sums of certain infinite series. Those series form a subset of the geometric
series, so I can obtain the same theorem almost trivially by deduction, which
gives me a good basis for comparing induction and deduction.

(This is not to take any glory away from Katy. Her report gives us an astonishing piece of work for something coming from a high-school student, a girl only beginning her study of truly abstract mathematics.)

Katy begins with a unit fraction, then adds its square, then its cube, then its fourth power, and so on. By carrying out the additions with the decimal equivalents of the fractions, she could see that the running sum seemed to converge upon some limiting value as the number of terms increased toward infinity. For her first three series she gives us

(Eq'n 1)

(Eq'n 2)

and

(Eq'n 3)

From those few examples she induced a general rule: for any number N we have as true to mathematics

(Eq'n 4)

Next she took the same series and removed the even-numbered powers of the initial unit fraction to get

(Eq'n 5)

(Eq'n 6)

and

(Eq'n 7)

From those examples she induced the rule that

(Eq'n 8)

Taking her next step, Katy changed her approach. She took the series that she wanted to examine in its abstract form,

(Eq'n 9)

and guessed that

(Eq'n 10)

She tested that guess with N=2, expecting to have S=2/7. Instead, as she added up the terms in the series, she saw the running sum approaching the limit S=4/7. So she modified her guess to

(Eq'n 11)

and tested it with N=3. She expected that series to add up to 9/26 and she found that it did so, confirming the correctness of her formula in Equation 11.

Finally Katy laid out her results;

(Eq'n 12)

(Eq'n 13)

and

(Eq'n 14)

Then she induced her general result. She noted that the first series consists of the sum of all of the powers of the first term; the second series consists of the same except that she has skipped every second term; and the third consists of the first series except that she has skipped every second and third term. Using y to represent the number of successive terms skipped in the series, she presented her result as

(Eq'n 15)

To obtain that same result by deduction,
using the standard method of summing an infinite geometric series, we need only
note that every term in any given Katy series differs from the preceding term by
a factor of (1/N)^{y+1}. We multiply the series by that factor and
subtract the product from the original series, which subtraction leaves the
first term of the original series, a unit fraction, as the remainder, so we have

(Eq'n 16)

A little simple algebraic manipulation, solving for S, converts that equation into Equation 15. Bim! Bam! Boom! Done! or, more formally, Q.E.D.

Contrast the two techniques described above.

I described the full set of Katy series with the maximum possible degree of algebraic abstraction. From my statement you would know that you could create a Katy series by positing a unit fraction and then generating the subsequent terms in the series by repeatedly multiplying that fraction by some positive power of itself.

Katy describes a series that consists of the sum of all of the positive powers of a unit fraction. She then describes other series in the set of Katy series by specifying a pattern of skipping or removing terms from that basic series. At no point does she say that the Katy series represent a subset of the geometric series; she doesn't mention the fact that the neighboring terms in her series have a common ratio. Thus she presents her series at the most primitive stage of algebraic abstraction, the stage at which all mathematical reasoning began.

Having in mind the general formula describing the Katy series, I multiplied it by the general form of the common ratio, using Katy's notation for the number of terms skipped, subtracted the product from the original series, which left only the first term as a remainder, and then applied a little simple algebra to obtain a general formula, Equation 15, for the sum of the series. So there we have a relatively trivial derivation for someone who first made algebra's acquaintance forty-six years ago (Fall 1960 in Mr. Disbrow's Algebra I class at Redwood High School in Visalia, California).

Using a geometric model, Katy showed us how the series with 2 as its first term and its common ration adds up, ultimately, to one. She then added the first half dozen or so terms of the series that have 1/3 and 1/4 as their first terms and common ratios and inferred, from her observation that the running sums seemed to approach certain limits, that each series adds up, ultimately, to a unit fraction. From those three examples she inferred a simple rule for calculating the sum of the series and, by induction, inferred that the rule applies to all series for which the first term and the common ratio consist of the same unit fraction.

In making those inferences Katy relied on relatively simple pattern recognition. She simply recognized that the decimal expression of each of her running sums seemed to approach, step by diminishing step, a familiar decimal fraction, either 0.3333... or 0.2500.... After converting those decimals into their equivalent unit fractions, she saw a simple relationship between the denominators of each series first term and sum. By assuming that series based on unit fractions with progressively larger denominators would still add up to unit fractions, she extended her simple rule for calculating the sum of the series to cover all possible series based on the same unit fraction as both the series first term and its common ratio.

The essence of induction consists of discerning a pattern in a subset of objects and then asserting that the pattern applies to the whole set. Once Katy had inferred that her first three series each add up to a unit fraction, she induced that all of the series of the same kind add up to a unit fraction. And when she saw the relationship between those unit fractions and the first terms in their respective series, she induced that the rule that she inferred expressing that relationship also applies to all series of the same kind. But we must take care with our discernment of patterns. An old joke has a mathematician, a physicist, and an engineer facing the challenge of proving and verifying the proposition that all odd numbers are prime: the mathematician proceeds by induction, saying, "one is prime, three is prime, five is prime, seven is prime, so by induction all odd numbers are prime."

In her second step Katy turned her attention to those series whose first terms are unit fractions and whose common ratios are squares of those unit fractions. She described those series as identical to the first set of her series with alternate terms removed or skipped in summing. Again she saw that her running sum of each series converged on a limit that she identified as a rational fraction. She certainly had no difficulty discerning a relationship between the numerators of those fractions and the first terms of their respective series. Finding the relationship between each fraction's denominator and its series first term offered more of a challenge and Katy met it. With those relationships in mind, she devised a rule for calculating the sum of each of those series and then extended it over all of the series in the set of Katy series that skip every other term.

After she had inferred that the first three elements of the set converged on rational fractions, insofar as she could tell, she induced in her mind that all elements of the set sum up to rational fractions. Her discovery that those fractions conform to a simple algebraic formula involving numbers appearing in the series only added confidence to that induction.

In approaching the third subset of her series, the series that differ from the original series by removal or skipping of every second and third term, she started with a hypothesis on the form of the formula for calculating the sum of each series in the subset. She tested that formula by applying it to the first series in the subset and then by beginning to sum the series term by term, only to find that the results did not match each other. She quickly saw that she had made a mistake in the form she gave the numerator in her hypothetical formula. She corrected the error and then retested the formula on the second series in the subset, finding that the rational fraction coming out of the corrected formula matched the rational fraction that she inferred as the limit of her term-by-term sum of the series.

With three formulae in mind, Katy was able to infer the more general formula that would yield the sum of any Katy series at all from its first term and the number of skipped terms. Again she discerned a pattern in a subset and assumed that it applied to the entire set. In so doing she applied yet again the process that mathematicians call incomplete induction, which stands on the principle of parsimony (also known as Occam's Razor). Until compelled by facts to do otherwise, we must assume the simplest explanation of any regularities that we discern in any set of mathematical objects, the explanation that requires the fewest premises.

Of course, we want to have mathematics as a purely axiomatic-deductive system. We prefer deduction over induction because where induction gives us probability, even strong likelihood, that a proposition conforms to the absolute truth underlying mathematics (the Platonic Form of Mathematics, if you prefer that term), deduction gives us certainty. But sometimes we need help getting to that certainty and induction can give us such a boost. Think of induction as the exploration of a landscape that precedes the arrival of the surveyors and the mapmakers.

In that metaphor Katy has done the Daniel Boone work on this infinite geometric series. Remaining at a relatively low level of abstraction, she laid out an infinite series comprising a unit fraction and all of its higher integer powers, the denominator of that unit fraction ranging over all of the natural numbers greater than one, and then added elements to that set by describing how to remove terms from each series "by hand" (as mathematicians say). She then did the hard work of calculating the sums of some of those series, inferred formulae for calculating those sums more conveniently, and then forged those formulae into a general formula for the sum of any series in the set. We might give in to temptation and say that Katy couldn't see the for the trees; but, then, we can't hope to understand the forest unless we know the trees.

Although this stands as a trivial example, Katy's work would provide guidance for a proper deduction if she were exploring more demanding mathematical terrain. Using Katy's description of her series, I recast it by describing the initial term and some power of that term as the common ratio between successive terms. With the resulting more abstract (more general) description of the series in mind, I then employed a very old and very simple trick to devise the formula for the sum of that series. All of our knowledge of mathematics should come so easily. And with students like Katy pursuing the subject someday it will.

Appendix: Geometric Proof

Katy opened her essay by describing how Mr. Cohen had suggested to her that she take a square, divide it into halves, color one half, then divide the uncolored half into halves, and repeat the process. Through that process of coloring the square by successive halves, coloring in alternating rectangles and squares, she demonstrated graphically that

(Eq'n 17)

She might then have separated that series into two subseries; Subseries 1 consisting of the sum of all of the odd powers of 2 (represented by the rectangles in her diagram) and Subseries 2 consisting of the sum of all of the even powers of 2 (representing the squares in her diagram). Clearly Subseries 1 adds up to twice as much as does Subseries 2, so she could have inferred easily that

(Eq'n 18)

That means, of course, that Subseries 1, the first element of the Skip-One subset of the Katy series, adds up to 2/3.

Katy then notes that summing the powers of 1/3 with diagrams would be trickier. But tricky does not mean impossible. Draw a square and divide it vertically into three equally-wide rectangles. Color the left rectangle red, color the right rectangle blue, and divide the central rectangle into three squares. Color the upper square red, color the lower square blue, and divide the central square vertically into three equally-wide rectangles. Repeat that procedure endlessly. Aside from a rotation by 180 degrees, the red zone matches the blue zone perfectly and the two zones together cover the whole initial square, so now we know that

(Eq'n 19)

Again, we can separate that series into Subseries 1 (representing the rectangles in the red area) and Subseries 2 (representing the squares in the red area) and infer readily that

(Eq'n 20)

and thence that the second element of the Skip-One subset of the Katy series adds up to 3/8. Let me just suggest that the reader try that derivation for the series that has 1/5 as its first term and common ratio.

Thus we see how Katy convinced herself that her series add up to rational fractions and how she might have taken the geometric stage of her analysis farther.

aaaefefefbbb