APPENDIX 2

Mathematical Background

A2.1 Introduction

Mathematics is one of the outstanding accomplishments of the human mind. Its abstract models of real-life phenomena have fostered advances in every field of science and engineering. Most of computer science is based on mathematics, and this book is no exception. This appendix provides an introduction to those mathematical concepts referred to in the chapters. Some exercises are given at the end of the appendix, so that you can practice the skills while you are learning them.

A2.2 Functions and Sequences

An amazing aspect of mathematics, first revealed by Whitehead and Russell [1910], is that only two basic concepts are required. Every other mathematical term can be built up from the primitives set and element. For example, an ordered pair < a, b > can be defined as a set with two elements:

< a, b > = {a, {a, b}}

The element a is called the first component of the ordered pair, and b is called the second component. Given two sets A and B, we can define a function f from A to B, written

f : A → B

as a set of ordered pairs < a, b >, where a is an element of A, b is an element of B, and each element in A is the first component of exactly one ordered pair in f. Thus no two ordered pairs in a function have the same first element. The sets A and B are called the domain and co-domain, respectively.

For example,

f = {< −2,4 >, < −1,1 >, < 0,0 >, < 1,1 >, < 2,4 >}

defines the "square" function with domain { −2, −1, 0, 1, 2 } and co-domain { 0, 1, 2, 4 }. No two ordered pairs in the function have the same first component, but it is legal for two ordered pairs to have the same second component. For example, the pairs

<-1, 1> and <1, 1>

have the same second component, namely, 1.

If< a, b> is an element of f, we write f(a) = b. This gives us a more familiar description of the above function: the function f is defined by

f(i) = i², for i in −2…2.

Another name for a function is a map. This is the term used in Chapters 12, 14, and 15 to describe a collection of elements in which each element has a unique key part and a value part. There is, in effect, a function from the keys to the values, and that is why the keys must be unique.

A finite sequence t is a function such that for some positive integer k, called the length of the sequence, the domain of t is the set { 0, 1, 2, …, k-1 }. For example, the following defines a finite sequence of length 4:

t(0) = "Karen"

t(1) = "Don"

t(2) = "Mark"

t(3) = "Courtney"

Because the domain of each finite sequence starts at 0, the domain is often left implicit, and we write

t = "Karen", "Don", "Mark", "Courtney"

A2.3 Sums and Products

Mathematics entails quite a bit of symbol manipulation. For this reason, brevity is an important consideration. An example of abbreviated notation can be found in the way that sums are represented. Instead of writing

Xo + Xi + X2 + ... + Xn-1

we can write

This expression is read as "the sum, as i goes from 0 to n −1, of xsub i." We say that i is the count index. A count index corresponds to a loop-control variable in a for statement. For example, the following code will store in sum the sum of components 0 through n-1 in the array x:

double sum = 0.0;
for (i = 0; i < n;
   sum += x [i];

Of course, there is nothing special about the letter "i." We can write, for example,

as shorthand for

1 + 1/2 + 1/3 + ... + 1/10

Similarly, if n > = m,

is shorthand for

m 2^-m + (m+1)2^-(m+1) + ... + n 2^-n

Another abbreviation, less frequently seen than summation notation, is product notation. For example,

is shorthand for

a [0] * a [1] * a [2] * a [3] * a [4]

A2.4 Logarithms

John Napier, a Scottish baron and part-time mathematician, first described logarithms in a paper he published in 1614. From that time until the invention of computers, the principal value of logarithms was in number-crunching: logarithms enabled multiplication (and division) of large numbers to be accomplished through mere addition (and subtraction).

Nowadays, logarithms have only a few computational applications—for example, the Richter scale for measuring earthquakes. But logarithms provide a useful tool for analyzing algorithms, as you saw (or will see) in Chapter 3 through 15.

We define logarithms in terms of exponents, just as subtraction can be defined in terms of addition, and division can be defined in terms of multiplication.

Given a real number b > 1, we refer to b as the base. The logarithm, base b, of any real number x > 0, written

^logb^x

is defined to be that real number y such that

b^y = x

For example, log₂16 = 4 because 2⁴ = 16. Similarly, log₁₀100 = 2 because 10² = 100. What is log₂ 64? What is log₈ 64? Estimate log₁₀ 64.

The following relations can be proved from the above definition and the corresponding properties of exponents. For any real value b > 1 and for any positive real numbers x and y,

From these equations, we can obtain the formula for converting logarithms from one base to another. For any bases a and b> 1 and for any X> 0,

log_b x = log_b a^{log a x} {by property 5}

= (log_a x)(log_b a){by property 7}

The base e e are called natural logarithms and are written in the shorthand ln instead of loge.

To convert from a natural logarithm to a base 2 logarithm, we apply the base-conversion formula just derived. For any x > 0,

ln x = (log₂ x )(ln2)

Dividing both sides of this equation by ln 2, we get

log₂ x = ln x / ln2

We assume the function ln is predefined, so this equation can be used to approximate log₂x. Similarly, using base-10 logarithms,

^log2 ^x = ^log10 ^{x / >log}10²

The function ln and its inverse exp provide one way to perform exponentiation. For example, suppose we want to calculate x^y where x and y are of type double and x > 0. We first rewrite x^y:

x^y = e^ln(x)y {by Property 6, above}

= e^{y ln x} {by Property 7}

This last expression can be written in Java as

Math.exp  (y * Math.ln  (x))

or, equivalently, and without any derivation,

Math.pow  (x, y)

A2.5 Mathematical Induction

Many of the claims in the analysis of algorithms can be stated as properties of integers. For example, for any positive integer n,

In such situations, the claims can be proved by the Principle of Mathematical Induction.

To help you to understand why this principle makes sense, suppose that S₁, S₂, … is a sequence of statements for which cases 1 and 2 are true. By case 1, S₁ must be true. By case 2, since S₁ is true, S₂ must be true. Applying case 2 again, since S₂ is true, S₃ must be true. Continually applying case 2 from this point, we conclude that S₄ is true, and then that S₅ is true, and so on. This indicates that the conclusion in the principle is reasonable.

To prove a claim by mathematical induction, we first state the claim in terms of a sequence of statements S₁, S₂, …. We then show that S₁ is true—this is called the base case. Finally, we need to prove case 2, the inductive case.

Here is an outline of the strategy for a proof of the inductive case: let n be any positive integer and assume that S_n is true. To show that S_n+1 is true, relate S_n+1 back to S_n, which is assumed to be true. The remainder of the proof often utilizes arithmetic or algebra.

An important variant of the Principle of Mathematical Induction is the following:

The difference between this version and the previous version is in the inductive case. Here, when we want to establish that S_n+1 is true, we can assume that S₁, S₂, …, S_n are true.

Before you go any further, try to convince (or at least, persuade) yourself that this version of the principle is reasonable. At first glance, you might think that the strong form is more powerful than the original version. But in fact, they are equivalent.

We now apply the strong form of the Principle of Mathematical Induction to obtain a simple but important result.

while (n > 1)
      n = n / 2;

In the original and "strong" forms of the Principle of Mathematical Induction, the base case consists of a proof that S1 is true. In some situations we may need to start at some integer other than 1. For example, suppose we want to show that

n! > 2ⁿ

for any n> = 4. (Notice that this statement is false for n = 1, 2, and 3.) Then the sequence of statements is S4, S5, … For the base case we need to show that S4 is true.

In still other situations, there may be several base cases. For example, suppose we want to show that

fib(n)< 2ⁿ

for any positive integer n. (The method fib, defined in Lab 7, calculates Fibonacci numbers.) The base cases are:

fib (1)< 2¹

and

fib (2)< 2²

These observations lead us to the following:

The general form extends the strong form by allowing the sequence of statements to start at any integer (K) and to have any number of base cases (S_K, S_K+1v.., S_L). If K = L = 1, the general form reduces to the strong form.

The next two examples use the general form of the Principle of Mathematical Induction to prove claims about Fibonacci numbers.

You could now proceed, in a similar fashion, to develop the following lower bound for Fibonacci numbers:

fib(n )>(6/5)ⁿ

for all integers n ≥ 3.

Hint: Use the general form of the Principle of Mathematical Induction, with K = 3and L = 4.

Now that lower and upper bounds for Fibonacci numbers have been established, you might wonder if we can improve on those bounds. We will do even better. In the next example we verify an exact, closed formula for the nth Fibonacci number. A closed formula is one that is neither recursive nor iterative.

The next example establishes part 1 of the Binary Tree Theorem in Chapter 9: the number of leaves is at most the number of elements in the tree plus one, all divided by 2.0. The induction is on the height of the tree and so the base case is for single-item tree, that is, a tree of height 0.

The next example, relevant to Chapter 12, shows that the height of any red-black tree is logarithmic in n.

A2.6 Induction and Recursion

Induction is similar to recursion. Each has a number of base cases. Also, each has a general case that reduces to one or more simpler cases, which, eventually, reduce to the base case(s). But the direction is different. With recursion, we start with the general case and, eventually, reduce it to the base case. With induction, we start with the base case and use it to develop the general case.

CONCEPT EXERCISES

A2.1 Use mathematical induction to show that, in the Towers of Hanoi game from Chapter 5, moving n disks from pole a to pole b requires a total of 2ⁿ - 1 moves for any positive integer n.

A2.2 Use mathematical induction to show that for any positive integer n,

where A is a constant and f is a function.

A2.3 Use mathematical induction to show that for any positive integer n,

A2.4 Let n₀ be the smallest positive integer such that

fib(n₀)>n²₀

1. Find n₀.
2. Use mathematical induction to show that, for all integers n ≥ n₀,

fib (n) > n²

A2.5 Show that fib(n) is exponential in n, specifically,

Hint: See the formula in Example A1.4 above. Note that the absolute value of

becomes insignificant for sufficiently large n.

A2.6 Show that

for any nonnegative integer n.

A2.7 Find the flaw in the following proof.

Claim All dogs have the same hair color.

Proof For n = 1,2 let S_n be the statement:

In any set of n dogs, all dogs in the set have the same hair color.

Base Case: If n = 1, there is only one dog in the set, so all dogs in that set have the same hair color. Thus, S1 is true.

Inductive Case: Let n be any positive integer and assume that S_n is true; that is, in any set of n dogs, all the dogs in the group have the same hair color. We need to show that S_n+1 is true. Suppose we have a set of n + 1 dogs:

d₁, d₂, d₃....d_n, d_n+1

The set d1, d2, d3, …, dn has size n, so by the Induction hypothesis, all the dogs in that set have the same hair color.

The set d₂, d₃ d_n, d_n+1 also has size n, so by the Induction hypothesis, all the dogs in that set have the same hair color.

But the two sets have at least one dog, d_n, in common. So whatever color that dog's hair is must be the color of all dogs in both sets, that is, of all n + 1dogs. In other words, S_n+1 is true.

Therefore, by the Principle of Mathematical Induction, S_n is true for any non-negative integer n.