How to Design Programs: An Introduction to Computing and Programming

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:

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:

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.

;; 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))

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.⁵¹ 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)
  (cond
    [(= 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.

Section 23 Mathematical Examples

23.1 Sequences and Series

23.2 Arithmetic Sequences and Series

23.3 Geometric Sequences and Series

Taylor Series

23.4 The Area Under a Function

23.5 The Slope of a Function

Section 23

Mathematical Examples