Section 23

Mathematical Examples

Applying mathematics to real-world problems requires programs that implement mathematical functions. In many cases, the programs also employ functions that consume and produce functions. Mathematics is therefore a great starting point for practicing programming with functions and, more generally, for creating abstract functions.

The first subsection covers sequences and series, a key element of mathematics. The second section discusses integration, which relies heavily on series. Finally, the third section introduces function differentiation.

23.1  Sequences and Series

In pre-algebra and algebra, we encounter sequences (also known as progressions) of numbers. Here are three examples:

  1. 0, 2, 4, 6, 8;

  2. 1, 3, 5, 7, 9;

  3. 5, 10, 15, 20, 25.

The first two enumerate the first five even and odd natural numbers, respectively; the last one lists the first five positive integers, evenly divisible by 5. Sequences can also be infinite:

  1. 0, 2, 4, 6, 8, ...;

  2. 1, 3, 5, 7, 9, ...;

  3. 5, 10, 15, 20, 25, ...

Following mathematical tradition, infinite sequences end in ``...'' and the reader must determine how to find more of the terms in the sequence.

One way to understand sequences of numbers, especially infinite ones, is to match them up with an enumeration of the natural numbers. For example, the even and odd (natural) numbers match up like this:


It is easy to see from this table that every even number is 2 · i for its index i and that an odd number is 2 · i + 1.

Both statements can be translated into simple Scheme functions:

;; make-even : N  ->  N[even]
;; to compute the i-th even number
(define (make-even i)
  (* 2 i))
;; make-odd : N  ->  N[odd]
;; to compute the i-th odd number
(define (make-odd i)
  (+ (* 2 i) 1))
In short, functions from natural numbers to numbers are representations of infinite sequences.

A mathematical series is the sum of a sequence. The three finite sequences have the sums 20, 25, and 75, respectively. In the case of infinite sequences it is often interesting to consider a finite portion, staring with the first one.51 For example, adding the first 10 even numbers yields 90, and adding the first 10 odd numbers yields 100. Computing a series is clearly a job for a computer. Here are functions that add up the first n odd or even numbers, respectively, using make-even and make-odd to compute the required numbers:

;; series-even : N  ->  number
;; to sum up the first
;; n even numbers
(define (series-even n) (cond [(= n 0) (make-even n)] [else (+ (make-even n) (series-even (- n 1)))]))
;; series-odd : N  ->  number
;; to sum up the first
;; n odd numbers
(define (series-odd n) (cond [(= n 0) (make-odd n)] [else (+ (make-odd n) (series-odd (- n 1)))]))

The two functions are natural candidates for abstraction and here is the result of following our basic abstraction recipe:

;; series : N (N  ->  number)  ->  number
;; to sum up the first n numbers in the sequence a-term,
(define (series n a-term)
    [(= n 0) (a-term n)]
    [else (+ (a-term n)
	     (series (- n 1) a-term))]))

The first argument specifies where the addition starts. The second argument of series is a function that maps a natural number to the corresponding term in the series. To test series, we apply it to make-even and make-odd:

;; series-even1 : N  ->  number
(define (series-even1 n)
  (series n make-even))	
;; series-odd1 : N  ->  number
(define (series-odd1 n)
  (series n make-odd))

For over a century, mathematicians have used the Greek symbol Sigma to communicate about series. The two series above would be expressed as


A true (lazy) mathematician would also replace make-even and make-odd by their definitions, that is, 2 · i and 2 · i + 1, but we refrain from doing so to emphasize the analogy to our (well-organized) functions.

Exercise 23.1.1.                    Use local to create series-local from series-even and series-odd. Show with a hand-evaluation that (series-local make-even) is equivalent to series-even.    Solution

23.2  Arithmetic Sequences and Series

In an arithmetic sequence


each successor term an+1 is the result of adding a fixed constant to an. Here is a concrete example, matched up with the natural numbers:


Here the starting point is 3 and the constant is 5. From these two facts, called starting point and summand, respectively, all other terms in the sequence can be determined.

Exercise 23.2.1.   Develop the recursive function a-fives, which consumes a natural number and recursively determines the corresponding term in the above series.    Solution

Exercise 23.2.2.   Develop the non-recursive function a-fives-closed. It consumes a natural number and determines the corresponding term in the above series. A non-recursive function is sometimes called a closed form.    Solution

Exercise 23.2.3.   Use series to determine the sum of the a-fives sequence for the bounds 3, 7, and 88. Can an infinite arithmetic series have a sum?    Solution

Exercise 23.2.4.   Develop the function seq-a-fives, which consumes a natural number n and creates the sequence of the first n terms according to a-fives or a-fives-closed. Hint: Use build-list.    Solution

Exercise 23.2.5.   Develop arithmetic-series. The function consumes two numbers: start and s. Its result is a function that represents the arithmetic series whose starting point is start and whose summand is s. For example, (arithmetic-series 3 5) yields a-fives (or a-fives-closed). Similarly, (arithmetic-series 0 2) produces a function that represents the series of even numbers.    Solution

23.3  Geometric Sequences and Series

In a geometric sequence


each succesor term gn+1 is the result of multiplying a fixed constant with gn. Here is a concrete example, matched up with the natural numbers:


Here the starting point is 3 and the constant is 5. From these, called starting point and factor, respectively, every other term in the sequence is determined.

Exercise 23.3.1.   Develop the recursive function g-fives, which consumes a natural number and recursively determines the corresponding term in the above geometric sequence.    Solution

Exercise 23.3.2.   Develop the non-recursive function g-fives-closed. It consumes a natural number and determines the corresponding term in the above series.    Solution

Exercise 23.3.3.   Develop the function seq-g-fives, which consumes a natural number n and creates the sequence of the first n terms according to g-fives or g-fives-closed. Hint: Use build-list.    Solution

Exercise 23.3.4.   Develop geometric-series. The function consumes two numbers: start and s. Its result is a function that represents the geometric series whose starting point is start and whose factor is s. For example, (geometric-series 3 5) yields g-fives (or g-fives-closed).    Solution

Exercise 23.3.5.   Use series to determine the sum of the g-fives sequence for the bounds 3, 7, and 88. Use series to determine the sum of (geometric-series 1 .1) for the bounds 3, 7, 88. Can an infinite geometric series have a sum?    Solution

Taylor Series

Mathematical constants like [curriculum-Z-G-D-1.gif] and e or functions like sin, cos, log are difficult to compute. Since these functions are important for many daily engineering applications, mathematicians have spent a lot of time and energy looking for better ways to compute these functions. One method is to replace a function with its Taylor series, which is, roughly speaking, an infinitely long polynomial.

A Taylor series is the sum of a sequence of terms. In contrast to arithmetic or geometric sequences, the terms of a Taylor series depend on two unknowns: some variable x and the position i in the sequence. Here is the Taylor series for the exponential function:


That is, if we wish to compute ex for any specific x, we replace x with the number and determine the value of the series. In other words, for a specific value of x, say, 1, the Taylor series becomes an ordinary series, that is, a sum of some sequence of numbers:


While this series is the sum of an infinitely long sequence, it actually is a number, and it often suffices to add just the first few terms to have an idea what the number is.

The key to computing a Taylor series is to formulate each term in the underlying sequence as a function of x and its position i. In our running example, the Taylor sequence for the exponential function has the shape


Assuming a fixed x, here is an equivalent Scheme definition:

;; e-taylor : N  ->  number
(define (e-taylor i)
  (/ (expt x i) (! i)))

;; ! : N  ->  number
(define (! n)
    [(= n 0) 1]
    [else (* n (! (sub1 n)))]))

The first function computes the term; the second computes the factorial of a natural number. To compute the value of ex, we now just need to ask for (series 10 e-taylor), assuming we want the first 10 items of the sequence included.

Putting everything together, we can define a function that computes the xth power of e. Since the function requires two auxiliaries, we use a local:

(define (e-power x)
  (local ((define (e-taylor i)
	    (/ (expt x i) (! i)))
	  (define (! n)
	      [(= n 0) 1]
	      [else (* n (! (sub1 n)))])))
    (series 10 e-taylor)))

Exercise 23.3.6.   Replace 10 by 3 in the definition of e-power and evaluate (e-power 1) by hand. Show only those lines that contain new applications of e-taylor to a number.

The results of e-power are fractions with large numerators and denominators. In contrast, Scheme's built-in exp function produces an inexact number. We can turn exact fractions into inexact numbers with the following function:

;;  exact-> inexact : number [exact]  ->  number [inexact] 

Test the function and add it to e-power's body. Then compare the results of exp and e-power. Increase the number of items in the series until the difference between the results is small.    Solution

Exercise 23.3.7.   Develop the function ln, which computes the Taylor series for the natural logarithm. The mathematical definition of the series is


This Taylor series has a value for all x that are greater than 0.

DrScheme also provides log, a primitive for computing the natural logarithm. Compare the results for ln and log. Then use exact->inexact (see exercise 23.3.6) to get results that are easier to compare.    Solution

Exercise 23.3.8.   Develop the function my-sin, which computes the Taylor series for sin, one of the trigonometric functions. The Taylor series is defined as follows:


It is defined for all x.

Hint: The sign of a term is positive if the index is even and negative otherwise. Mathematicians compute ( - 1)i to determine the sign; programmers can use cond instead.    Solution

Exercise 23.3.9.   Mathematicians have used series to determine the value of [curriculum-Z-G-D-1.gif] for many centuries. Here is the first such sequence, discovered by Gregory (1638-1675):


Define the function greg, which maps a natural number to the corresponding term in this sequence. Then use series to determine approximations of the value of [curriculum-Z-G-D-1.gif].

Note on [curriculum-Z-G-D-1.gif]: The approximation improves as we increase the number of items in the series. Unfortunately, it is not practical to compute [curriculum-Z-G-D-1.gif] with this definition.    Solution

23.4  The Area Under a Function

Consider the function graph in figure 64. Suppose we wish to know the area between the x axis, the fat lines labeled a and b, and the graph. Determining the area under the graph of a function for some specific interval is called integrating a function. Since engineers had to solve this kind of problem before computers were available, mathematicians have studied it extensively. For a small class of functions, it is indeed possible to determine the area exactly. For the other cases, mathematicians have developed several methods to determine close estimates. Since these methods involve lots of mechanical calculations, they are natural candidates for computer functions.



Figure 64:  Integrating a function f between a and b

A general integration function must consume three inputs: a, b, and the function f. The fourth part, the x axis, is implied. This suggests the following contract:

;; integrate : (number  ->  number) number number  ->  number
;; to compute the area under the graph of f between a and b
(define (integrate f a b) ...)

Kepler suggested one simple integration method. It consists of three steps:

  1. divide the interval into two parts: [a,(a + b/2)] and [(a + b/2),b];

  2. compute the area of each trapezoid; and

  3. add the two areas to get an estimate at the integral.

Exercise 23.4.1.   Develop the function integrate-kepler. It computes the area under some the graph of some function f between left and right using Kepler's rule.    Solution

Another simple method is to think of the area as a sequence of many small rectangles. Each rectangle is as tall as the function graph in, say, the middle of the rectangle. Figure 64 shows two examples. By adding up the area of the rectangles, we get a good estimate at the area under the graph. The more rectangles we consider, the closer the estimate is to the actual area.

Let us agree that R stands for the number of rectangles that we wish to consider. To determine how large these rectangles are, we need to figure out how large their sides are. The length of the side on the x axis is the length of the interval divided by the number of rectangles:


For the height of the rectangle, we need to determine its midpoint and then the value of f at the midpoint. The first midpoint is clearly at a plus half of the width of the rectangle, that is, if


the area is


where W stands for width and S for step from now on.

To get from the rectangle starting at a to the next one on the right, we must add the width of one rectangle. That is, the next midpoint (called x1 in figure 64) is at


the third one at


and so on. The following table explains the three sequences that are involved in the usual manner:


In the second row, M stands for midpoint. The first rectangle has index 0, the last one R - 1.

Using this sequence of rectangles, we can now determine the area under the graph as a series:


Exercise 23.4.2.   Develop the function integrate. It computes the area under some the graph of some function f between left and right using the rectangle-series method.

Use test cases for f, a, and b for which one can determine the area exactly and easily by hand, for example, (define (id x) x). Compare the results with those of integrate from exercise 23.4.1.

Make R a top-level constant:

;; R : number of rectangles to approximate integral
(define R ...)

Test integrate on sin and increase R gradually from 10 to 10000. What happens to the result?    Solution

23.5  The Slope of a Function

Let us take another look at the function graph in figure 64. For many problems, we need to be able to draw a line that has the same slope as some curve at a certain point. Indeed, computing the slope is often the true goal. In economics problems, the slope is the growth rate of a company if the curve represents the income over time. In a physics problem, the curve could represent the velocity of some object; its slope, at any point, is then the current acceleration of the object.

Determining the slope of some function f at some point x is to differentiate the function. The differential operator (also called a functional) returns a function f' (pronounced ``f prime''). It tells us for any x what the slope of f is at that point. Computing f' is complicated, so it is again a good task for a computer program. The program consumes some function f and produces f'.

Figure 65:  The graph of some function

To design a ``differentiator'' we must study how we could construct lines that have the same slope as a curve. In principle, such a line touches the curve at just that point. But suppose we relax this constraint for a moment and look at straight lines that intersect the curve close to the point of interest. We pick two points that are equally far away from x, say, x - [curriculum-Z-G-D-2.gif] and x + [curriculum-Z-G-D-2.gif]; the constant [curriculum-Z-G-D-2.gif], pronounced epsilon, represents some small distance. Using the two corresponding points on the curve, we can determine a straight line that has the proper slope.

The situation is sketched in figure 65. If the point of interest has coordinate x, the two points are (x,f(x - [curriculum-Z-G-D-2.gif])) and (x,f(x + [curriculum-Z-G-D-2.gif])). Hence the slope of the line is


That is, the difference between the height of the right point and the left point divided by their horizontal distance. Determining the line from the slope and one of the points or even from two points is an exercise.

Exercise 23.5.1.   The equation for a line is


By now, it is straightforward to translate this equation into Scheme:

(define (y x)
  (+ (* a x) b))

To obtain a concrete line we must replace a and b with numbers.

The teachpack provides one operation for drawing lines: graph-line. The operation consumes a line like y and a color, say, 'red. Use graph-line to draw the graphs of the following lines:

  1. y1(x) = x + 4

  2. y2(x) = 4 - x

  3. y3(x) = x + 10

  4. y4(x) = 10 - x

  5. y5(x) = 12


Exercise 23.5.2.   It is a standard mathematical exercise to develop the equation for a line from a point on the line and its slope. Look up the method in your mathematics book. Then develop the function line-from-point+slope, which implements the method. The function consumes a posn (the point) and a number (the slope). It produces a function that represents the line in the spirit of exercise 23.5.1.

Testing a function-producing function like line-from-point+slope can be done in two ways. Suppose we apply the function to (0,4) and 1. The result should be line y1 from exercise 23.5.1. To check this, we can either apply the result of

(line-from-point+slope (make-posn 0 4) 1)

to some numbers, or we can draw the result using the operations in In the first case, we must use y1 to compare outputs; in the second case we can draw the result in one color and the hand-constructed line in a different one and observe the effect.    Solution

Once we have an intersecting line through (x,f(x - [curriculum-Z-G-D-2.gif])) and (x,f(x + [curriculum-Z-G-D-2.gif])), we can also get a line with the proper slope. By decreasing [curriculum-Z-G-D-2.gif] until it is (almost) indistinguishable from 0, the two intersection points move closer and closer until they are one, namely, (x,f(x)), the point for which we wish to know the slope.52

Exercise 23.5.3.   Use the operation graph-fun in the teachpack to draw the mathematical function


The operation works just like draw-line (see exercise 23.5.1.)

Suppose we wish to determine the slope at x = 2. Pick an [curriculum-Z-G-D-2.gif] > 0 and determine the slope of the line that goes through (x,f(x - [curriculum-Z-G-D-2.gif])) and (x,f(x + [curriculum-Z-G-D-2.gif])) with the above formula. Compute the line with line-from-point+slope from exercise 23.5.2 and use draw-line to draw it into the same coordinate system as y. Repeat the process with [curriculum-Z-G-D-2.gif]/2 and then with [curriculum-Z-G-D-2.gif]/4.    Solution

If our goal is to define the differential operator as a Scheme function, we can approximate it by setting [curriculum-Z-G-D-2.gif] to a small number and by translating the mathematical formula into a Scheme expression:

;; d/dx : (num  ->  num)  ->  (num  ->  num)
;; to compute the derivative function of f numerically
(define (d/dx f)
  (local ((define (fprime x)
	    (/ (- (f (+ x [curriculum-Z-G-D-2.gif])) (f (- x [curriculum-Z-G-D-2.gif])))
	       (* 2 [curriculum-Z-G-D-2.gif])))
	  (define [curriculum-Z-G-D-2.gif] ...))

Note that d/dx consumes and produces functions -- just like the differential operator in mathematics.

As mentioned in the introduction to this section, the differential operator computes the function f' from some function f. The former computes the slope of f for any x. For straight lines, the slope is always known. Hence a function that represents a straight line is an ideal test case for d/dx. Let us consider

(define (a-line x)
  (+ (* 3 x) 1))

The evaluation of (d/dx a-line) proceeds as follows:

  (d/dx a-line)

= (local ((define (fprime x)
	    (/ (- (a-line (+ x [curriculum-Z-G-D-2.gif])) (a-line (- x [curriculum-Z-G-D-2.gif])))
	       (* 2 [curriculum-Z-G-D-2.gif])))
	  (define [curriculum-Z-G-D-2.gif] ...))

= (define (fprime x)
    (/ (- (a-line (+ x [curriculum-Z-G-D-2.gif])) (a-line (- x [curriculum-Z-G-D-2.gif])))
       (* 2 [curriculum-Z-G-D-2.gif])))
  (define [curriculum-Z-G-D-2.gif] ...)

Now, if we think of (+ x [curriculum-Z-G-D-2.gif]) and (- x [curriculum-Z-G-D-2.gif]) as numbers, we can evaluate the application of a-line in the definition of fprime:53

  (define (fprime x)
    (/ (- (+ (* 3 (+ x [curriculum-Z-G-D-2.gif])) 1) (+ (* 3 (- x [curriculum-Z-G-D-2.gif])) 1))
       (* 2 [curriculum-Z-G-D-2.gif])))

= (define (fprime x)
    (/ (- (* 3 (+ x [curriculum-Z-G-D-2.gif])) (* 3 (- x [curriculum-Z-G-D-2.gif])))
       (* 2 [curriculum-Z-G-D-2.gif])))

= (define (fprime x)
    (/ (* 3 (- (+ x [curriculum-Z-G-D-2.gif]) (- x [curriculum-Z-G-D-2.gif])))
       (* 2 [curriculum-Z-G-D-2.gif])))

= (define (fprime x)
    (/ (* 3 (* 2 [curriculum-Z-G-D-2.gif]))
       (* 2 [curriculum-Z-G-D-2.gif])))

= (define (fprime x)

In other words, the result of (d/dx a-line) always returns 3, which is the slope of a-line. In short, we not only got a close approximation because [curriculum-Z-G-D-2.gif] is small, we actually got the correct answer. In general, however, the answer will depend on [curriculum-Z-G-D-2.gif] and will not be precise.

Exercise 23.5.4.   Pick a small [curriculum-Z-G-D-2.gif] and use d/dx to compute the slope of


at x = 2. How does the result compare with your calculation in exercise 23.5.3?    Solution

Exercise 23.5.5.   Develop the function line-from-two-points. It consumes two points p1 and p2. Its result is a Scheme function that represents the line through p1 and p2.

Question: Are there any situations for which this function may fail to compute a function? If so, refine the definition to produce a proper error message in this case.    Solution

Exercise 23.5.6.   Compute the slope of the following function

(define (f x) 
  (+ (* 1/60 (* x x x))
     (* -1/10 (* x x))

at x = 4. Set [curriculum-Z-G-D-2.gif] to 2, 1, .5. Try the same for some other value of x.    Solution

51 In some cases, an infinite sequence may also have a sum. Specifically, adding up more and more of the terms of a sequence produces numbers that are closer and closer to some number, which we call the sum. For example, the sum of the sequence


is 2. In contrast, the sequence


does not have a sum.

52 The process of decreasing [curriculum-Z-G-D-2.gif] to 0 is a convergence (or limit) process. It does not always succeed, that is, for some function graphs, the process does not end properly. We ignore those cases, but they are common and require special attention.

53 If x is a number, then adding or subtracting [curriculum-Z-G-D-2.gif] yields a number. If, by accident, we apply fprime to something else, both expressions signal an error. It is therefore acceptable to act as if the expressions were values. In general, this is not true.