1 The Bridge Between Continuous and Discrete

[Pages:18]1 The Bridge Between Continuous and Discrete

1.1 Introduction

In the early 1730s, Leonhard Euler (1707?1783) astonished his contemporaries

by solving one of the most burning mathematical puzzles of his era: to find

the

exact

sum

of

the

infinite

series

1 1

+

1 4

+

1 9

+

1 16

+

1 25

+???,

whose

terms

are

the reciprocal squares of the natural numbers. This dramatic success began

his rise to dominance over much of eighteenth-century mathematics. In the

process of solving this then famous problem, Euler invented a formula that

simultaneously completed another great quest: the two-thousand-year search

for closed expressions for sums of numerical powers. We shall see how Euler's

success with both these problems created a bridge connecting continuous and

discrete summations.

Sums

for

geometric

series,

such

as

1 1

+

1 2

+

1 4

+

1 8

+ ???

=

2,

had

been

known since antiquity. But mathematicians of the late seventeenth century

were captivated by the computation of the sum of a series with a completely

different type of pattern to its terms, one that was far from geometric. In the

late 1660s and early 1670s, Isaac Newton (1642?1727) and James Gregory

(1638?1675) each deduced the power series for the arctangent,1 arctan t =

t-

t3 3

+

t5 5

-

???,

alternating series

which produces, when evaluated

of

reciprocal

odd

numbers

1

-

1 3

at t = 1, the sum

+

1 5

-

1 7

+

1 9

-

?

?

?

4

for

[133,

the pp.

492?494], [135, pp. 436?439]. And in 1674, Gottfried Wilhelm Leibniz (1646?

1716), one of the creators of the differential and integral calculus, used his

new calculus of infinitesimal differentials and their summation (what we now

call

integration )

to

obtain

the

same

value,

4

,

for

this

sum

by

analyzing

the

quadrature, i.e., the area, of a quarter of a unit circle [133, pp. 524?527].

Leibniz and the Bernoulli brothers Jakob (1654?1705) and Johann (1667?

1748), from Basel, were tantalized by this utterly unexpected connection

1 This power series had also been discovered in southern India around two hundred years earlier, where it was likely derived for astronomical purposes, and written in verse [125], [133, pp. 494?496].

2

1 The Bridge Between Continuous and Discrete

between the special number from geometry and the sum of such a sim-

ple and seemingly unrelated series as the alternating reciprocal odd numbers.

What could the connection be? They began considering similar series, and it

is not surprising that they came to view the sum of the reciprocal squares,

first mentioned in 1650 by Pietro Mengoli (1626?1686), as a challenge. De-

spite hard work on the problem, success eluded the Bernoullis for decades, and

Jakob wrote, "If someone should succeed in finding what till now withstood

our efforts and communicate it to us, we shall be much obliged to him" [258,

p. 345]. The puzzle was so prominent that it became known as the "Basel

problem."

Around 1730, Euler, a student of Johann Bernoulli's, took a completely

fresh approach to the Basel problem by placing it in a broader context. He

decided to explore the general discrete summation

n i=1

f (i)

of

the

values

of

an arbitrary function f (x) at a sequence of natural numbers, where n may be

either finite or infinite. The Basel problem, to

context, since the sum can be written as

i=1

find g(i)

for it=h1ei12fu, nficttsioinntgo(xth)is=nxe12w.

Euler's broader approach also encompassed an age-old question, that of finding

formulas for sums of numerical powers, as we will now explain.

By the sixth century b.c.e., the Pythagoreans already knew how to find

a sum of consecutive natural numbers, which we write as

1 + 2 + 3 + ? ? ? + n = n i1 = n(n + 1) = n2 + n .

2

22

i=1

Archimedes of Syracuse (c. 287?212 b.c.e.), the greatest mathematician of antiquity, also discovered how to calculate a sum of squares. Translated into contemporary symbolism, his work shows that

12 + 22 + 32 + ? ? ? + n2 = n i2 = n(n + 1)(2n + 1) = n3 + n2 + n .

6

3 26

i=1

Throughout the next two millennia, the search for general formulas for

n i=1

ik ,

a

sum

of

consecutive

kth

powers

for

any

fixed

natural

number

k,

be-

came a recurring theme of study, primarily because such sums could be used

to find areas and volumes. All these previous efforts also fit within Euler's gen-

eral context, since they are simply

n i=1

fk (i)

for

the

functions

fk (x)

=

xk .

While the function g for the Basel problem is very different from the functions

fk that produce sums of powers, Euler's bold vision was to create a general

approach to any sum of function values at consecutive natural numbers.

Euler's aim was to use calculus to relate the discrete summation

n i=1

f

(i)

(with n possibly infinity) to a continuous phenomenon, the antiderivative, i.e.,

the integral

n 0

f (x)dx.

We

know

that

these

two

provide

first

approximations

to each other, since the sum can be interpreted as the total area of rectangles

with tops forming a staircase along the curve y = f (x), while the antideriva-

tive, appropriately evaluated between limits, can be interpreted as the area

1.1 Introduction

3

y

y = xk

. . . 12

x n ?1 n

Fig. 1.1. Comparing a discrete sum with a continuous area.

under the curve itself (Figure 1.1). It is precisely the delicate difference, in both numerical value and in concept, between such discrete sums and continuous areas that mathematicians had in fact been exploring for so long when trying to find formulas for sums of powers.

For such powers the discrete sum is

n

n

fk(i) = ik = 1k + 2k + 3k + ? ? ? + nk,

i=1

i=1

while the continuous quantity for comparison is

n

fk(x)dx =

0

n

xkdx =

nk+1 .

0

k+1

Notice that the latter provides the first term in each of the polynomial sum-

mation formulas displayed above from the Pythagoreans and Archimedes. Un-

derstanding the dynamic between discrete and continuous amounts to quanti-

fying exactly how separated, distinct, and finite objects blend with connected,

homogeneous, and infinite spaces. Scholars as far back as Zeno, in classical

Greece, grappled with this tension. Out of the fog of using discrete sums to

approximate areas emerged the discovery of the differential and integral calcu-

lus in the seventeenth century. We shall see that Euler then turned the tables

around in the eighteenth century by applying calculus to solve problems of

the discrete.

Euler reconciled the difference between a discrete sum and a continuous

iansttehgerafil rvsitaaappstrroixkiimngatfioornmtuolathuesisnugmamcaotriroensponni=di1nfg(ai)n,twidiethrivaadtdiviteion0nafl

(x)dx terms

utilizing the iterated derivatives of f to make the necessary adjustments from

continuous to discrete. Today we call this the Euler?Maclaurin summation

formula. Euler applied it to obtain incredibly accurate approximations to the

sum of the reciprocal squares, for solving the Basel problem, and these suc-

cesses

likely

enabled

him

to

guess

that

the

infinite

sum

was

exactly

2 6

.

Armed

4

1 The Bridge Between Continuous and Discrete

with this guess, it was not long before he found a proof, and announced a solution of the Basel problem to the mathematical world.

Euler's correspondents were greatly impressed. Johann Bernoulli wrote, "And so is satisfied the burning desire of my brother [Jakob], who, realizing that the investigation of the sum was more difficult than anyone would have thought, openly confessed that all his zeal had been mocked. If only my brother were alive now" [258, p. 345].

Euler also used his summation formula to provide closure to the long search for closed formulas for sums of powers. By now this thread had wound its way from classical Greek mathematics through the medieval Indian and Islamic worlds and into the Renaissance. Finally, during the Enlightenment, Jakob Bernoulli discovered that the problem revealed a special sequence of numbers, today called the Bernoulli numbers. These numbers became a key feature of Euler's summation formula and of modern mathematics, since, as we shall soon see, they capture the essence of converting between the continuous and the discrete. We will trace this thread through original sources from Archimedes to Euler, ending with Euler's exposition of how his general summation formula reveals formulas for sums of powers as well as a way to tackle the Basel problem. That Euler used his summation formula to resolve these two seemingly very different problems is a fine illustration of how generalization and abstraction can lead to the combined solution of seemingly independent problems.

Fig. 1.2. Square, rectangular, and triangular numbers.

We return now to the very beginning of our story, which revolves around the relationship between areas and formulas for discrete sums of powers, such as the closed formulas above for the sums of the first n natural numbers and the first n squares. For the natural numbers it is not hard both to discover and to verify the formula oneself, but the Pythagoreans would not have written it as we do. For them, number was the substance of all things. Numbers were probably first represented by dots in the sand, or pebbles. From this, patterns in planar configurations of dots began to be recognized, and these were related to areas of planar regions, as in Figure 1.2 [18, p. 54f], [113], [133, p. 48ff], [135, p. 28ff], [258, p. 74ff].

1.1 Introduction

5

In the figure, the arrangement and number of dots in each configuration

suggests general closed formulas for various types of sums, illustrated by the

three types 1+3+5+7+9 = 52, 2+4+6+8+10 = 5?6, and 1+2+3+4+5 =

(5 ? 6) /2 = 15. The reader may easily conjecture and prove general summation

formulas with n terms for each of these.

For the third type, the total number of dots in the triangular pattern is

clearly half of that in the rectangular pattern, which can be verified in general

either algebraically, or geometrically from Figure 1.2. Thus we have deduced

the closed Pythagorean formula above for the sum of natural numbers,2 and

we

also

see

why

the

numbers

n(n+1) 2

(i.e.,

1,

3,

6,

10,

15,

. . .)

deserve

to

be

called triangular numbers. Notice that each of the three types of sums of dots

has for its terms an arithmetic progression, i.e., a sequence of numbers with a

fixed difference between each term and its successor. The first and third types

always begin with the number one; the Pythagoreans realized that such sums

produce polygonal numbers, i.e., those with dot patterns modeled on triangles,

squares, pentagons, etc. (Exercises 1.1, 1.2).

The closed formula for a sum of squares, which we pulled from thin air

earlier, is implicit in the work of Archimedes. At first sight it may seem un-

expected that such a discrete sum should even have a closed formula. Once

guessed, though, one can easily verify it by mathematical induction (Exer-

cise 1.3). The formula arises in two of Archimedes' books [7]. In Conoids and

Spheroids Archimedes develops and uses it as a tool for finding volumes of

paraboloids, ellipsoids, and hyperboloids of revolution. In Spirals he applies

it to obtain a remarkable result on the area enclosed by a spiral, stated thus

in his preface:

If a straight line of which one extremity remains fixed be made to revolve at a uniform rate in a plane until it returns to the position from which it started, and if, at the same time as the straight line revolves, a point move at a uniform rate along the straight line, starting from the fixed extremity, the point will describe a spiral in the plane. I say then that the area bounded by the spiral and the straight line which has returned to the position from which it started is a third part of the circle described with the fixed point as the centre and with radius the length traversed by the point along the straight line during the one revolution.

2 Another way of obtaining this formula occurs in a story about the developing genius Carl F. Gauss (1777?1855). When Gauss was nine, his mathematics teacher, J. G. Bu?ttner, gave his class of 100 pupils the task of summing the first 100 integers. Gauss almost immediately wrote 5050 on his slate and placed it on his teacher's desk. Gauss had noticed that adding the numbers first in the corresponding pairs 1 and 100, 2 and 99, 3 and 98, . . . , produced the sum 101 exactly 50 times, and then he simply multiplied 101 by 50 in his head. Fortunately, Bu?ttner recognized Gauss's genius, and arranged for special tutoring for him. Gauss became the greatest mathematican of the nineteenth century [133, p. 654].

6

1 The Bridge Between Continuous and Discrete

Fig. 1.3. Archimedes' area of a spiral.

Figure 1.3 illustrates Archimedes' claim that the area OP QAO within the spiral is exactly one-third the area AKP Q A of the "first circle."

Our original source will focus on Archimedes' expression for a sum of squares, and the resulting theorem on the area of the spiral, using the classical Greek method of exhaustion. Here we will see an early historical link between the discrete, in the form of the sum of squares formula, and the continuous, namely the area bounded by a continuous curve.

We will see also that Archimedes does not actually need an exact sum of squares formula to find the area in his spiral, but rather only the inequalities

n3 3<

n

i2

<

(n

+ 1)3 3,

i=1

which are highly suggestive of a more general pattern related to antidifferen-

tiation of the kth-power functions fk(x) = xk (Exercises 1.4, 1.5).

Our mathematical forebears were extremely interested in formulas for sums

of higher powers

n i=1

ik ,

since

they

could

use

these

to

compute

other

areas

and volumes. Let us pause to review from modern calculus how sums of powers

are explicitly involved in the interpretation of the area under the curve y = xk,

for 0 x 1, as the definite integral

1 0

xk

dx.

Recall

that

to

calculate

this

area from its modern definition as a limit of Riemann sums, we can subdivide

the interval into n equal subintervals, each of width 1/n, and consider the

sum of areas of the rectangles built upwards to the curve from, say, the right

endpoints of these subintervals, obtaining

n i=1

1 n

?

= i k

n

1 nk+1

n i=1

ik

as

an approximation to the area under the curve. The exact area is then the

limit of this expression as n approaches infinity, since increasing n refines the

accuracy of the approximation. Thus it is clear why having a closed formula

for

n i=1

ik

(or

perhaps

just

inequalities

analogous

to

those

of

Archimedes

1.1 Introduction

7

above) is key for carrying this calculation to completion. While this modern

formulation streamlines the verbal and geometric versions of our ancestors,

still the algebraic steps were essentially these.

As we continue to powers higher than k = 2, a formula for

n i=1

i3

jumps

off the page once we compute a few values and compare them with our pre-

vious work. (The reader who wishes to guess the formula before we intro-

duce it may consult Exercise 1.6 now.) It seems likely, from the work of the

neo-Pythagorean Nicomachus of Gerasa in the first century c.e., that the

mathematicians of ancient Greece knew this too; while it is not explicit in

extant work, it is implicit in a fact about sums of odd numbers and cubic

numbers found in Nicomachus's Introductio Arithmetica [19], [113, p. 68f]

(Exercise 1.7).

The general formula for a sum of cubes first appears explicitly in the A?ryabha.t?iya, from India [133, p. 212f], a book of stanzas perhaps intended as a short manual for memorization, which A? ryabhat.a wrote in 499 c.e., when he was 23 years old. Without any proof or justification, and in the completely

verbal style of ancient algebra, he wrote:

The sixth part of the product of three quantities consisting of the number of terms, the number of terms plus one, and twice the number of terms plus one is the sum of the squares. The square of the sum of the (original) series is the sum of the cubes.

The earliest proof we have of the sum of cubes formula is by the Islamic mathematician Abu? Bakr al-Karaj?i (c. 1000 c.e.), one of a group who began to develop algebra, in particular generalizing the arithmetic of numbers, centered around the House of Wisdom established in Baghdad in the ninth century [133, p. 251ff]. Al-Karaj?i's argument is noteworthy for its use of the method of "generalizable example" [113, p. 68f], [133, p. 255].

The idea of a generalizable example is to prove the claim for a particular number, but in a way that clearly shows that it works for any number. This was a common method of proof for centuries, in part because there was no notation adequate to handle the general case, and in particular no way of using indexing as we do today to deal with sums of arbitrarily many terms. Al-Karaj?i proves that (1 + 2 + 3 + ? ? ? + 10)2 = 13 + 23 + 33 + ? ? ? + 103 in a way that clearly generalizes: He considered the square ABCD with side 1 + 2 + ? ? ? + 10 (Figure 1.4), subdivided into gnomons (L-shaped pieces) as shown, with the largest gnomon having ends BB = DD = 10. The area of the largest gnomon is 103 (the reader should carry this "calculation" out in a way that is convincing of "generalizibility"). By the same generalized reasoning the area of the next-smaller gnomon is 93, and so on for all the smaller gnomons, with only a square of side 1 left over.

Now one can think of the area of the large square in two ways. As the sum of gnomons it has area 1+23 +33 +? ? ?+103. On the other hand, as a square it has area (1+2+3+? ? ?+10)2. Today we would be inclined to use an algebraic proof by mathematical induction here; but it appears unnecessary if one sees how

8

1 The Bridge Between Continuous and Discrete

B

C

B

. . .

9 10

A

D

D

Fig. 1.4. Gnomons for the sum of cubes (not to scale).

to break the square up into gnomons, each identifiable numerically as a cube. This could all be done algebraically, although it would be excruciating, which is what leads us to use mathematical induction if we are invoking algebra rather than geometry (Exercise 1.8).

At this point we can be optimistic that for each fixed natural number k there is a polynomial in n for 1k +2k +3k +? ? ?+nk. Based on our examples and the analogy to integration of xk, the reader should try to guess the degree of the polynomial, the leading coefficient, and inequalities that might bound the polynomial like those of Archimedes. On the other hand, no general pattern is yet emerging for the details of the formula for various values of k, and worse, all the formulas we obtained emerged from ad hoc methods, each demanding separate verification.

The work of the Egyptian mathematician Abu? `Al?i al-H. asan ibn alHaytham (965?1039) gives us the first steps along a path toward understanding these formulas in general [133, p. 255f]. He needed a sum of fourth powers in order to find the volume of a general paraboloid of revolution (in contemporary terms this involves integrating x4). At that time, Islamic mathematicians were studying, rediscovering, and extending the work of Archimedes and others on volumes by the method of exhaustion. Ibn al-Haytham's specific expression for fourth powers came from his equation (expressed here in modern symbolism) connecting sums of powers for different exponents:

n

n

n

(n + 1) ik = ik+1 +

p

ik .

i=1

i=1

p=1 i=1

Although ibn al-Haytham did not state a completely general result, rather only

for n = 4 and k = 1, 2, 3, his proof, like al-Karaj?i's, clearly generalizes for all n

and k from his example, and uses a kind of mathematical induction (Exercise

1.9). In fact we can also prove his equation by interchanging the order of

the double summation (Exercise 1.10). Letting k = 3, one can now obtain a

formula for

n i=1

i4,

as

did

ibn

al-Haytham,

by

solving

for

it

in

his

equation,

first substituting the known formulas for smaller exponents. He did this, again

by generalizable example. This is not quite as easy as we have made it sound,

though, since in the process the double summation will actually give rise to the

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download